有一个方格矩阵,矩阵边界在无穷远处。我们做如下假设:
a. 每走一步时,只能从当前方格移动一格,走到某个相邻的方格上;
b. 走过的格子立即塌陷无法再走第二次;
c. 只能向北、东、西三个方向走;
请问:如果允许在方格矩阵上走n步,共有多少种不同的方案。2种走法只要有一步不一样,即被认为是不同的方案。
Input允许在方格上行走的步数n(n <= 20)Output计算出的方案数量Sample Input
2
Sample Output
7
解题思路:用深度搜索,搜索方向只有三个。起点用i > 20的数组(设置边界)
#include <iostream> #include <cstring> using namespace std; int vis[50][20]; int dir[3][2]={{1,0},{0,1},{-1,0}}; int n,num,step = 0; void dfs(int x, int y){ if( step == n) { num++;return; }//步数等于n,num++; if(vis[x][y]) return;//如果是旧点,直接返回 step++;//步数+1 vis[x][y] = 1;//设置为旧点 for(int i = 0; i < 3; i++){ //向三个方向搜索 int dx = x + dir[i][0]; int dy = y + dir[i][1]; if(!vis[dx][dy]) dfs(dx,dy); } step--; //回溯,步数减一 vis[x][y] = 0;//回溯把旧点变为新点 return; } int main(){ while(cin>>n){ num = 0; memset(vis,0,sizeof(vis)); dfs(25,0); cout<<num<<endl; } return 0; }