总时间限制: 1000ms 内存限制: 65536kB

描述

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

1. 每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；
2. 走过的格子立即塌陷无法再走第二次；
3. 只能向北、东、西三个方向走；

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

输入

允许在方格上行走的步数n(n ≤ 20)

输出

计算出的方案数量

样例输入

2

样例输出

7

思路

• 递归

从(i, j)出发, 走n步的方案数, 等于以下三项之和:

• 从(i+1, j)出发, 走n-1步的方案数. 前提: (i+1, j)还没走过
• 从(i, j+1)出发, 走n-1步的方案数. 前提: (i, j+1)还没走过
• 从(i, j-1)出发, 走n-1步的方案数. 前提: (i, j-1)还没走过

代码

#include <iostream>
#include <cstring>
using namespace std;
int visited[30][50];
int Ways(int row, int col, int steps) {
    if( steps == 0 )
        return 1;
    visited[row][col] = 1;  // 该方块被访问了
    int num = 0;
    if( !visited[row][col-1] )  // 西进
        num += Ways(row, col-1, steps-1);
    if( !visited[row][col+1] )  // 东进
        num += Ways(row, col+1, steps-1);
    if( !visited[row+1][col] )  // 北进
        num += Ways(row+1, col, steps-1);
    visited[row][col] = 0;  // 重新置为未访问, 为了给上一层的其他节点用
    return num;
}
int main() {
    int N;
    cin >> N;
    memset(visited, 0x0, sizeof(visited));
    /* 从(0, 25)出发, 可以避免越界 */
    cout << Ways(0, 25, N) << endl;
    return 0;
}