解题思路:
n不超过20,先写一个dfs爆搜。
因为是二维数组,所以把只能向上、左、右走改成了向下、左、右走,起始位置在(0,50),这样向下左右走不会超过边界。
先将起始位置标记为-1,表示不能返回。
以走三步为例,所有可能走过的位置如图所示:
参考代码:
#include <iostream> using namespace std; int dx[3]={1,0,0};//下 左 右 int dy[3]={0,-1,1}; int dp[107][107]; int n,z; void dfs(int x1,int y1,int k) { if(k==n){//走了n步,计数+1 z++; return; } for(int i=0; i<3; i++) {//三个方向 int x=x1+dx[i],y=y1+dy[i]; if(dp[x][y]!=-1) {//如果没有走过 dp[x][y]=-1;//标记为走过 dfs(x,y,k+1);//向下一方向搜索 dp[x][y]=1;//因为要回溯,所以重新标记为没有走过 } } } int main() { cin>>n; dp[0][50]=-1;//起始点标记为-1 dfs(0,50,0); cout<<z<<endl; //打印查看 // for(int i=0; i<5; i++) { // for(int j=45; j<55; j++)cout<<dp[i][j]<<" \n"[j==54]; // } return 0; }
0.0分
154 人评分