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

【noi 2.5_1792】迷宫（bfs 或 dfs）

2018-06-17 23:48:40来源：未知阅读 ()

简单搜索，在n*n的矩阵中，问从起点是否可以到达终点，有些格子不可走，上下左右四个方向都可以走。(N<=100)
1.bfs从起点开始走，直到走到终点或全部遍历过一次就结束。
2.dfs要一走到终点就返回，否则4^n会TLE。由于询问“是否可到达终点”，就直接递归“是否可以走到点（x,y)点”的函数，也是直到找到终点就结束。

下面附上dfs的代码——

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 using namespace std;
 6 #define N 110
 7 
 8 char s[N][N];
 9 int v[N][N],a[4]={1,-1,0,0},b[4]={0,0,1,-1};
10 int n,xx,yy;
11 
12 int goit(int x,int y)
13 {
14     if (x<0||y<0||x>=n||y>=n) return 0;
15     if (s[x][y]=='#'||v[x][y]) return 0;
16     if (x==xx && y==yy) return 1;
17     v[x][y]=1;
18     for (int i=0;i<4;i++)
19       if (goit(x+a[i],y+b[i])) return 1;
20     return 0;
21 }
22 
23 int main()
24 {
25     //freopen("a.in","r",stdin);
26     int T;
27     scanf("%d",&T);
28     while (T--)
29     {
30       scanf("%d",&n);
31       for (int i=0;i<n;i++)
32         scanf("%s",s[i]);
33       memset(v,0,sizeof(v));
34       int x,y;
35       scanf("%d%d%d%d",&x,&y,&xx,&yy);
36       int tf=goit(x,y);
37       if (tf) printf("YES\n");
38       else printf("NO\n");
39     }
40     return 0;
41 }