迷宫问题的求解（广度和深度优先搜索）

时间：2022-10-06 20:30:52

     迷宫问题主要可以分为两类，一个是深度优先搜索和广度优先搜索。

     广度优先搜索常用于求最优解(如最短时间，最优路径等)，站在一个点上，首先试一试自己周围的点是否可以走，如果是路则加入待走队列，如果是墙则丢弃。迷宫问题在广度优先搜索的时候需要特别注意的就是要及时抛弃，遇到走过的点立即丢弃，遇到墙立即丢弃，不然时间复杂度就很高。一般利用队列来辅助。

      深度优先搜索则不需最优的特性，用于求解有或者没有的问题。一般利用堆栈或递归来实现。

      下面先介绍简单的二叉树的广度和深度优先遍历

 

 1 //广度优先遍历
 2 void BFS(Tree root)
 3 {
 4     queue<Node>Q;
 5     Q.push(root);
 6     Node temp;
 7     while( Q.empty()==false){
 8         template = Q.front();
 9         Q.pop();
10         printf("%d",temp->data);
11         if( temp->lchild){
12             Q.push(temp->lchild);
13         }
14         if( temp->rchild){
15             Q.push(temp->rchild);
16         }
17     }
18 
19 }

 

 1 //深度优先遍历
 2 void DFS( Tree root)
 3 {
 4     stack <Node> S;
 5     S.push(root);
 6     Node node;
 7     while( S.empty()){
 8         node = S.top();
 9         printf("%d",node->data);
10         S.pop();
11         if( node->rchild){
12             S.push(node->rchild);
13         }
14         if( node->lchild){
15             S.push( node->lchild);
16         }
17     }
18 }

 

胜利大逃亡

 

题目描述

Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会. 

魔王住在一个城堡里,城堡是一个A*B*C的立方体,可以被表示成A个B*C的矩阵,刚开始Ignatius被关在(0,0,0)的位置,离开城堡的门在(A-1,B-1,C-1)的位置,现在知道魔王将在T分钟后回到城堡,Ignatius每分钟能从一个坐标走到相邻的六个坐标中的其中一个.现在给你城堡的地图,请你计算出Ignatius能否在魔王回来前离开城堡(只要走到出口就算离开城堡,如果走到出口的时候魔王刚好回来也算逃亡成功),如果可以请输出需要多少分钟才能离开,如果不能则输出-1. 

<center> 迷宫问题的求解（广度和深度优先搜索）</center>

输入描述:

输入数据的第一行是一个正整数K,表明测试数据的数量.每组测试数据的第一行是四个正整数A,B,C和T(1<=A,B,C<=50,1<=T<=1000),它们分别代表城堡的大小和魔王回来的时间.然后是A块输入数据(先是第0块,然后是第1块,第2块......),每块输入数据有B行,每行有C个正整数,代表迷宫的布局,其中0代表路,1代表墙.(如果对输入描述不清楚,可以参考Sample Input中的迷宫描述,它表示的就是上图中的迷宫)
       

特别注意:本题的测试数据非常大,请使用scanf输入,我不能保证使用cin能不超时.在本OJ上请使用Visual C++提交.

输出描述:

对于每组测试数据,如果Ignatius能够在魔王回来前离开城堡,那么请输出他最少需要多少分钟,否则输出-1.
示例1

输入

1
3 3 4 20
0 1 1 1
0 0 1 1
0 1 1 1
1 1 1 1
1 0 0 1
0 1 1 1
0 0 0 0
0 1 1 0
0 1 1 0

输出

11
这道题一开始看题看半天，其实它就是3*3*4=36个点，是一个立体的图形，下面的0，1就是表示那个点是路还是墙
 1 #include<stdio.h>
 2 #include<queue>
 3 
 4 using namespace std;
 5 
 6 bool mark[50][50][50];  //标记数组
 7 int maze[50][50][50];   //保存立方体信息
 8 
 9 struct Node
10 {
11     int x,y,z;
12     int t;
13 };
14 queue<Node> Q;
15 
16 int go[][3]
17 {
18     1,0,0,
19     -1,0,0,
20     0,1,0,
21     0,-1,0,
22     0,0,1,
23     0,0,-1
24 };
25 
26 int BFS(int a,int b,int c)
27 {
28     int i;
29     Node temp;
30     while( Q.empty()==false)
31     {
32         Node now = Q.front();
33         Q.pop();
34         for( i=0; i<6; i++)
35         {
36             //依次扩展6个相邻结点
37             int nx = now.x+go[i][0];
38             int ny = now.y+go[i][1];
39             int nz = now.z+go[i][2];
40             if( nx<0 || nx>=a || ny<0 || ny>=b || nz<0|| nz>=c)
41                 continue;  //若再立方体外则丢弃
42             if( maze[nx][ny][nz]==1)
43                 continue;  //若为墙则丢弃
44             if( mark[nx][ny][nz]==true)
45                 continue;  //若访问过则丢弃
46 
47             temp.x = nx;
48             temp.y = ny;
49             temp.z = nz;
50             temp.t = now.t+1;
51             Q.push(temp);   //新位置加入队列中
52             mark[nx][ny][nz] = true;  //标记该位置
53             if( nx==a-1 && ny==b-1 && nz==c-1)
54                 return temp.t;  //到达终点
55         }
56     }
57     return -1;
58 }
59 int main()
60 {
61     int n;
62     int i,j,k;
63     int a,b,c,t;
64     int ret;
65     scanf("%d",&n);
66     while( n--)
67     {
68 
69         scanf("%d%d%d%d",&a,&b,&c,&t);
70         for( i=0; i<a; i++)
71         {
72             for( j=0; j<b; j++)
73             {
74                 for( k=0; k<c; k++)
75                 {
76                     scanf("%d",&maze[i][j][k]);
77                     mark[i][j][k] = false;
78                 }
79             }
80         }
81         while( Q.empty()==false) Q.pop();  //清空队列
82         mark[0][0][0] = true;  //标记起点
83         Node temp;
84         temp.t = temp.x = temp.y = temp.z=0;
85         Q.push(temp);
86         ret  = BFS( a,b,c);
87         if( ret<=t) printf("%d\n",ret);   //成功逃出输出时间，无法找到终点输出-1
88         else printf("-1\n");  //若时间超过返回-1
89     }
90     return 0;
91 }

 

Tempter of the bone

时间限制：1秒 空间限制：32768K 热度指数：148

题目描述

The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze. 

The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him. 

输入描述:

The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:
       

'X': a block of wall, which the doggie cannot enter; 
       
'S': the start point of the doggie; 
       
'D': the Door; or 
'.': an empty block.
       

The input is terminated with three 0's. This test case is not to be processed.

输出描述:

For each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise.
示例1

输入

4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0

输出

NO
YES

题目大意：有一个n*m的迷宫，包括起点s，终点d，墙x和地面，0秒时主人公从s出发，每秒能走到四个与其相邻的位置中的一个，且每个位置被行走之后都不能再次走入，问是否存在这样一条路径使在T秒刚好走到d

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 char maze[8][8];  //保存地图信息
 5 int n,m,t;
 6 int flag;  //是否找到的标记
 7 int go[][2]=
 8 {
 9     1,0,
10     -1,0,
11     0,1,
12     0,-1
13 };
14 
15 void DFS( int x,int y, int time)
16 {
17     int i;
18     int nx,ny;
19     for( i=0; i<4; i++)
20     {
21         //枚举四个相邻位置
22 
23         int nx = x + go[i][0];
24         int ny = y + go[i][1];
25         if( nx<1 || nx>n || ny<1 || ny>m) continue;
26         if( maze[nx][ny]=='X') continue;  //若该位置为墙，跳过
27         if( maze[nx][ny]=='D')  //若该位置为门
28         {
29             if( time+1 == t)
30             {
31                 //判断时间
32                 flag = 1 ;
33                 return;
34             }
35             else continue;
36         }
37 
38         maze[nx][ny] = 'X';  //修改该位置为墙
39         DFS( nx, ny, time+1);  //递归扩展该状态
40         maze[nx][ny] = '.';
41         if( flag==1 ) return;  //假如成功，直接返回
42     }
43 }
44 int main()
45 {
46     int i,j;
47     int sx,sy;
48     while( scanf("%d%d%d",&n,&m,&t)!=EOF)
49     {
50         if( n==0 && m==0 && t==0) break;
51 
52         for( i=1; i<=n; i++)
53         {
54             //建构迷宫
55             scanf("%s",maze[i]+1);
56         }
57         flag = 0;  //初始化成功标记
58         for( i=1; i<=n; i++)
59         {
60             for( j=1; j<=m; j++)
61             {
62                 if( maze[i][j]=='D')
63                 {
64                     //寻找D位置的坐标
65                     sx = i;
66                     sy = j;
67                 }
68             }
69         }
70         for( i=1; i<=n; i++)
71         {
72             for( j=1; j<=m; j++)
73             {
74                 if( maze[i][j]=='S' && (i+j)%2 ==((sx+sy)%2+t%2)%2 )
75                 {
76                     //找到S点
77                     maze[i][j] = 'X';
78                     DFS(i,j,0);
79 
80                 }
81             }
82         }
83         if( flag ) printf("YES\n");
84         else printf("NO\n");
85     }
86     return 0;
87 }

    这道题一开始剪枝不够提示超时，后加入 

    (i+j)%2 ==((sx+sy)%2+t%2)%2 

这个判断的意思是每走一步，只有一个坐标分量发生增一或减一的改变，那么两个坐标分量和的奇偶性将发生变化。
当走过奇数步时，其所在的位置坐标和的奇偶性和终点坐标和的奇偶性不同。走过偶数步时奇偶性相同

 

 

标签：

相关文章