1167. 迷宫
1167. 迷宫 (Standard IO)
时间限制: 1000 ms 空间限制: 262144 KB 具体限制
题目描述
设有一个N*N(2<=N<10)方格的迷宫，入口分别在左上角和右上角。迷宫格子中分别放0和1,0表示可通，1，表示不能通过，入口和出口肯定是0。迷宫走的规则如下：即从某个点开始，又八个方向可走，前进方格中的数字为0时表示可以通过，为1时表示不可通过，要另找路径。找出所有从入口（左上角）到出口（右上角）的路径（不能重复），输出路径总数，如果无法到达，则输出0。
输入
第一行输入N. 接下来N行，每行N个数字，0或1，描述迷宫。
输出
输出路径总数。
样例输入
3
0 0 0
0 1 1
1 0 0样例输出
2数据范围限制
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 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-03-24 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录