当前位置：首页 > news >正文

BFS 、DFS 解决迷宫入门问题

news 来源：原创 2024/5/8 3:20:36

问题 B: 逃离迷宫二

时间限制: 1 Sec 内存限制: 128 MB
提交: 12 解决: 5
[ 提交][ 状态][ 讨论版]

题目描述

王子深爱着公主。但是一天，公主被妖怪抓走了，并且被关到了迷宫。经过了常人难以想像的努力，王子到了这个迷宫，但是迷宫太过复杂，王子想知道到底有没有路能通到公主的所在地，同时还要输出王子到公主的最短距离，机智的你一定能帮助他解决这个问题。

输入

有多个测试数据。

每个测试数据的第一行是2个整数n,m （0<n<50, 0<m<50）代表着迷宫的高度和宽度。

接着是个n*m的迷宫抽象图。其中，'#'代表着墙壁,'.'代表着空地，'W'代表着王子的所在地。‘G’代表这公主的所在地，

王子只可以在空地上走，并且只能上，下，左，右的走。

输出

如果王子能到达公主的所在地，输出最短的距离

否则输出"Mission Failed"

样例输入

5 5 ##### #G..# ###.# #..W# #####

样例输出

DFS代码：

 1 #include<stdio.h>
 2 #include<malloc.h>
 3 #include<string.h>
 4 
 5 char Graph [80][80];
 6 int n,m,startx,starty;
 7 int Dir [4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
 8 int Vis [80][80];
 9 
10 int Fit(int x , int y){
11     return ( x>=1 && x<= n && y>=1 && y<= m );
12 }
13 
14 int DFS (int x,int y){
15     int i;
16     Vis [x][y] = 1;
17     for(i = 0 ; i < 4 ; i++ ){
18         int tmpx = x + Dir [i][0]; 
19         int tmpy = y + Dir [i][1]; 
20 
21         if(Fit (tmpx , tmpy) && Graph [tmpx][tmpy] == 'G'){
22             return 1;
23         }
24 
25         if(Fit (tmpx , tmpy) && Vis [tmpx][tmpy] == 0 && Graph [tmpx][tmpy] == '.'){
26             if (DFS (tmpx ,tmpy)){
27                 return 1;
28             }
29         }
30     }
31     return 0;
32 }
33 
34 int main(){
35     int i ,j ;
36     while(scanf("%d%d",&n,&m)!=EOF){
37         getchar();
38 
39         for( i=1 ; i <= n ; i++ ){
40             for( j=1 ; j<=m ; j++ ){
41                 Vis [i][j] = 0;
42                 scanf("%c", &Graph [i][j]);
43                 if(Graph [i][j] == 'W'){
44                     startx = i;
45                     starty = j;
46                 }
47             }
48             getchar();
49         }
50 
51         if(DFS(startx , starty)){
52             printf("Good life\n");
53         }
54         else{
55             printf("Mission Failed\n");
56         }
57     }
58     return 0;
59 }

BFS代码：

 1 #include<stdio.h>
 2 #include<malloc.h>
 3 #include<string.h>
 4 
 5 char Graph [80][80];//以二维数组记录图
 6 int n,m,startx,starty;
 7 int Dir [4][2] = {{1,0},{0,1},{-1,0},{0,-1}};//方向数组
 8 int Vis [80][80];//记录是否已经访问过
 9 int Dis [80][80];//记录遍历的层数
10 
11 int Fit(int x , int y){//判断是否超出边界
12     return ( x>=1 && x<= n && y>=1 && y<= m );
13 }
14 
15 int BFS (int x , int y){
16     int queue[9999];
17     int i , head = 0 , tail = 0;//head指向队列头，tail指向队列尾
18 
19     queue [tail++] = x ;
20     queue [tail++] = y ;
21     Vis [x][y] = 1 ;
22 
23     while(head < tail){//当队列为空停止搜索
24         int nowx = queue [head++];//取出队首x元素
25         int nowy = queue [head++];//取出队首y元素
26 
27         for(i = 0 ; i < 4 ; i++){
28             int tmpx = nowx + Dir [i][0];
29             int tmpy = nowy + Dir [i][1];
30 
31             if(Fit (tmpx,tmpy) && Graph [tmpx][tmpy] == 'G'){
32                 return Dis [nowx][nowy] + 1;//返回值为当前层数
33             }
34 
35             if(Fit(tmpx ,tmpy) && Vis [tmpx][tmpy] == 0 && Graph [tmpx][tmpy] == '.' ){
36                 //如果下层没有超出界限，并且没有访问过，并且为合法路径，则继续走下去
37                 Dis [tmpx][tmpy] = Dis [nowx][nowy] + 1;
38                 Vis [tmpx][tmpy] = 1;
39 
40                 queue [tail++] = tmpx;
41                 queue [tail++] = tmpy;
42             }
43         }
44     }
45     return 0;//如果出不了迷宫，则返回为0
46 }
47 
48 int main(){
49     int i ,j ;
50     while(scanf("%d%d",&n,&m)!=EOF){
51         getchar();
52 
53         for( i=1 ; i <= n ; i++ ){
54             for( j=1 ; j <= m ; j++ ){
55                 Vis [i][j] = 0;
56                 scanf("%c", &Graph [i][j]);
57                 if(Graph [i][j] == 'W'){
58                     startx = i;
59                     starty = j;
60                 }
61             }
62             getchar();
63         }
64 
65         int ans = 0;
66         ans = BFS(startx , starty);
67 
68         if(ans)
69             printf("%d\n",ans);
70         else
71             printf("Mission Failed\n");    
72     }
73     return 0;
74 }