首页 > > 程序设计 > C/C++ >

1167. 迷宫

2018-06-17 23:01:39来源：未知阅读 ()

题目描述

设有一个N*N(2<=N<10)方格的迷宫，入口分别在左上角和右上角。迷宫格子中分别放0和1,0表示可通，1，表示不能通过，入口和出口肯定是0。迷宫走的规则如下：即从某个点开始，又八个方向可走，前进方格中的数字为0时表示可以通过，为1时表示不可通过，要另找路径。找出所有从入口（左上角）到出口（右上角）的路径（不能重复），输出路径总数，如果无法到达，则输出0。

输入

第一行输入N.
接下来N行，每行N个数字，0或1，描述迷宫。

输出

输出路径总数。

样例输入

样例输出

数据范围限制

2<=N<10

 1 #include<iostream>
 2 using namespace std;
 3 int xx[9]={0,0,1,1,1,-1,-1,-1};
 4 int yy[9]={1,-1,1,0,-1,1,0,-1};
 5 int tot;
 6 int n;
 7 int a[101][101];
 8 int vis[101][101];
 9 void f(int x,int y)
10 {
11     if(x==1&&y==n)
12     {
13         tot++;
14         return;
15     }
16     else
17     {
18         for(int i=0;i<8;i++)
19         {
20             if(x+xx[i]>=1&&x+xx[i]<=n&&y+yy[i]>=1&&y+yy[i]<=n&&a[x+xx[i]][y+yy[i]]==0&&vis[x+xx[i]][y+yy[i]]==0)
21             {
22                 vis[x+xx[i]][y+yy[i]]=1;
23                 f(x+xx[i],y+yy[i]);
24                 vis[x+xx[i]][y+yy[i]]=0;
25             }
26         }
27     }
28 }
29 int main()
30 {
31     
32     cin>>n;
33     for(int i=1;i<=n;i++)
34     {
35         for(int j=1;j<=n;j++)
36         {
37             cin>>a[i][j];
38         }
39     }
40     a[1][1]=1;
41     f(1,1);
42     cout<<tot;
43     return 0;
44 }