1105 迷宫问题

【题目描述】

设有一个N*N方格的迷宫，入口和出口分别在左上角和右上角。迷宫格子中分别放有0和1，0表示可通，1表示不能，迷宫走的规则如下图所示：即从某点开始，有八个方向可走，前进方格中数字为0时表示可通过，为1时表示不可通过， 要另找路径。找出一条从入口（左上角）到出口（右上角）的路径(每个格子只能走一次)。

【输入格式】
只有一组输入数据。输入如下面样例，且1<N<15

【输出格式】
输出可行的路径总数。如果无法到达，输出0。
【输入样例】
3
0 0 0
0 1 1
1 0 0
【输出样例】
2

#include<iostream>
using namespace std;
const int N=20;
int n;
int g[N][N];
bool vis[N][N];
int dx[8]={
    -1,-1,0,1,-1,0,1,1};
int dy[8]={
    0,-1,-1,-1,1,1,1,0};
int res=0;
int dfs(int x,int y)
{
    if(x==0 && y==n-1)res++;for(int i=0;i<8;i++){
    int xx,yy;xx=x+dx[i];yy=y+dy[i];if(xx>=0 && yy>=0 && xx<n && yy<n && g[xx][yy]==0&&!vis[xx][yy]){
    vis[xx][yy]=true;dfs(xx,yy);vis[xx][yy]=false;}}return res;
}
int main()
{
    cin>>n;for(int i=0;i<n;i++){
    for(int j=0;j<n;j++)cin>>g[i][j];}vis[0][0]=true;cout<<dfs(0,0)<<endl;return 0;
}