有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：
a. 每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；
b. 走过的格子立即塌陷无法再走第二次；
c. 只能向北、东、西三个方向走；
请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。
Input允许在方格上行走的步数n(n <= 20)Output计算出的方案数量Sample Input
2
Sample Output
7
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<map>
using namespace std;
int n, ans = 0;
bool Map[30][50];
void dfs(int a, int b, int step) {
Map[a][b] = 1;
if (!step) {
ans++;
return;
}
if (!Map[a + 1][b]) {
dfs(a + 1, b, step - 1);
Map[a + 1][b] = 0;
}
if (!Map[a][b - 1]) {
dfs(a, b - 1, step - 1);
Map[a][b - 1] = 0;
}
if (!Map[a][b + 1]) {
dfs(a, b + 1, step - 1);
Map[a][b + 1] = 0;
}
}
int main() {
//freopen("in.txt", "r", stdin);
memset(Map, 0, sizeof(Map));
scanf("%d", &n);
dfs(0, 25, n);
printf("%d\n", ans);
return 0;
}