我把思路写在代码里面把,挺有意思的一道题。
第一次做这种迷宫题,可能代码不是很精简,继续努力,总体思路听清晰的。
#include<bits/stdc++.h>
using namespace std;
int n;
int maze[15][15];
int ans;
int vis[105][105];
void dfs(int row,int col){
if(row==0&&col==n-1){
ans++;//答案+1
return;//迷宫终点,结束递归
}
for(int i=row;i<n;i++){//每次遍历都是从当前节点开始,并且只遍历一个八个方向的节点
for(int j=col;j<n;j++){
if(maze[i][j]==0&&!vis[i][j]){//0表示此路可以走,并且没有走过
vis[i][j]=1;//标记此节点已经走过
if(row>0&&!vis[row-1][col]&&maze[row-1][col]==0){//判断该节点上面可不可以走
dfs(row-1,col);//可以走,进入递归,进入上面那个节点
vis[row-1][col]=0;//递归出来后取消标记
}
if((row<n-1)&&!vis[row+1][col]&&maze[row+1][col]==0){//判断该节点下面可不可以走
dfs(row+1,col);
vis[row+1][col]=0;
}
if(col>0&&!vis[row][col-1]&&maze[row][col-1]==0){//判断该节点左边可不可以走
dfs(row,col-1);
vis[row][col-1]=0;
}
if(col<n-1&&!vis[row][col+1]&&maze[row][col+1]==0){//判断该节点右边可不可以走
dfs(row,col+1);
vis[row][col+1]=0;
}
if((row>0&&col>0)&&!vis[row-1][col-1]&&maze[row-1][col-1]==0){//判断该节点左上方可不可以走
dfs(row-1,col-1);
vis[row-1][col-1]=0;
}
if((col<n-1&&row>0)&&!vis[row-1][col+1]&&maze[row-1][col+1]==0){//判断该节点右上面可不可以走
dfs(row-1,col+1);
vis[row-1][col+1]=0;
}
if((row<n-1&&col>0)&&!vis[row+1][col-1]&&maze[row+1][col-1]==0){//判断该节点左下方可不可以走
dfs(row+1,col-1);
vis[row+1][col-1]=0;
}
if((col<n-1&&row<n-1)&&!vis[row+1][col+1]&&maze[row+1][col+1]==0){//判断该节点右下方可不可以走
dfs(row+1,col+1);
vis[row+1][col+1]=0;
}
return;//important 如果不加这个return那么循环会继续遍历其他点这是我们不
//想看到的,如果判断完当前节点八个方向后直接return到进入该节点的那个点
}
}
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>maze[i][j];
}
}
dfs(0,0);//迷宫起点
cout<<ans<<endl;
}