踩方格—dfs

poj（1196）踩方格

【题目描述】
有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：

a、每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；

b、走过的格子立即塌陷无法再走第二次；

c、只能向北、东、西三个方向走；

请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。

【输入】
允许在方格上行走的步数n(n≤20)。

【输出】
计算出的方案数量。

【输入样例】
2
【输出样例】
7

 解题思路：

1，首先思路也是递归，从（i，j）出发，一共有三个方向可以走，那么用递归的思路想就是在这一点的方案数等于可以走的三个方向的方案数之和。

 代码：

#include 
using namespace std;
int visited[30][50];
int ways(int i, int j, int n) {
    //i 和j 是表示位置，n是方案数
    if (n == 0) {
        //这个地方就是递归的退出条件
        //如果这个地方的方案数是0那么就相当于站在原地，这个也是一种方案
        return 1;
    }
    //假设ij没有走过
    visited[i][j] = 1;
    int num;
    if (!visited[i][j-1]) {
        num += ways(i, j - 1,n - 1);
        //这个n-1就为递归的结束埋下了伏笔
    }
    if (!visited[i][j +1]) {
        num += ways(i, j + 1, n - 1);
    }
    if (!visited[i+1][j]) {
        num += ways(i + 1, j , n - 1);
    }
    visited[i][j] = 0;
    return num;
}
int main() {
    int n;
    cin >> n;
    memset(visited, 0, sizeof(visited));
    cout << ways(0, 25, n) << endl;
    return 0;
}

这里有一个并不好理解的地方就是这个为什么visited这个数组对应位置后面要再把这个值给归零。一开始不是已经把这个方块踩塌了吗？

  用我的话说就是一种走法初始化一次。每一种走法走完之后就要把一开始踩掉的方块给回复开始验证新一种走法，如果不回复的话肯定数量会少掉很多走法会被中断了。（不好配合这个图说，这样说我感觉有点太苍白了。）

  感觉写代码的能力还是不行，感觉好多东西不懂，多积累吧。