【题解】迷宫路线问题

#include<bits/stdc++.h>
using namespace std;
int ans=0 ,n;
//1.地图数组
int maze[10][10];
//2.标记数组
int used[10][10];
//3.方向数组
int fx[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}; 
//dfs 搜索
void dfs(int x,int y){
	//如果是终点，就ans+1,结束本次搜索
	if(x==1&&y==n){
		ans++;
		return ;
	} else{  
		used[x][y]=1;//标记当前点已经走过
		//按顺序寻找各个方向上联通的点
		for(int i=0;i<8;i++){
			int nx=x+fx[i][0];
			int ny=y+fx[i][1];
			//判断 nx和ny是否符合要求
			if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&used[nx][ny]==0&&maze[nx][ny]==0){
				used[nx][ny]=1;
				dfs(nx,ny);
				used[nx][ny]=0;
			} 
		}
		used[x][y]=0; 
	}
} 
int main(){

	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>maze[i][j];
		}
	}
	dfs(1,1);
	cout<<ans<<endl;
	return 0;
}