noj->电子老鼠走迷宫

00 问题

描述：

有一只电子老鼠被困在如下图所示的迷宫中。这是一个12*12单元的正方形迷宫，黑色部分表示建筑物，白色部分是路。电子老鼠可以在路上向上、下、左、右行走，每一步走一个格子。现给定一个起点S和一个终点T，求出电子老鼠最少要几步从起点走到终点。

输入：

本题包含一个测例。在测例的第一行有四个由空格分隔的整数，分别表示起点的坐标S（x.y）和终点的坐标T（x,y）。从第二行开始的12行中，每行有12个字符，描述迷宫的情况，其中'X'表示建筑物，'.'表示路.

输出：

输出一个整数，即电子老鼠走出迷宫至少需要的步数。

输入样例：

2 9 11 8
XXXXXXXXXXXX
X......X.XXX
X.X.XX.....X
X.X.XX.XXX.X
X.X.....X..X
X.XXXXXXXXXX
X...X.X....X
X.XXX...XXXX
X.....X....X
XXX.XXXX.X.X
XXXXXXX..XXX
XXXXXXXXXXXX

输出样例：

01 思路

01-1 类型

很明显的一个迷宫了，并且要求出电子老鼠最少要几步从起点走到终点，所以是广搜类型。

01-2 算法

第一步：设置入口出口和迷宫本体->init()函数
第二步：bfs主控函数：
- 队列入出循环
- 生成四个节点对四个节点进行判断
  - 如果新坐标为终点坐标，就返回路径长度
  - 其他点：如果不是终点坐标，在迷宫内，未访问过，不是墙，就入队
    - 入队操作：
```
x.push(nextx);
y.push(nexty);
used[nextx][nexty]=1;
step[nextx][nexty]=step[prex][prey]+1;
```
    - 完成入队出队闭环。
- 输出

02 代码

 1 //电子老鼠闯迷宫

 2 #include<iostream>

 3 #include<queue>

 4 

 5 using namespace std;

 6 

 7 int map[13][13];//迷宫本体

 8 int used[13][13]={0};//走过标记，0为未走，1为已走

 9 int step[13][13]={0};//到达当前节点所走的步数

10 int inx,iny,outx,outy,prex,prey,nextx,nexty;

11 //分别是入口，出口，老位置、新位置

12 int dx[4] = {-1,1,0,0};//左右上下

13 int dy[4] = {0,0,-1,1};//左右上下

14 

15 void init();

16 int bfs();

17 queue<int>x;

18 queue<int>y;

19 

20 int main(){

21     init();//初始化矩阵以及队列

22     cout<<bfs()<<endl;

23     return 0;

24 }

25 void init(){

26     int i,j;

27     char temp;

28     cin >> inx >> iny >> outx >> outy;

29     //初始化这个矩阵，方便起见，从1开始

30     for(i=1;i<13;i++){

31         for(j=1;j<13;j++){

32             cin>>temp;

33             if(temp == 'X'){

34                 map[i][j]=1;

35             }

36             else{

37                 map[i][j]=0;

38             }

39         }

40     }

41     //起点入队

42     x.push(inx);

43     y.push(iny);

44     used[inx][iny]=1;

45 }

46 int bfs(){//

47     int i;

48     while(!x.empty()&&!y.empty()){

49         prex = x.front();

50         prey = y.front();

51         x.pop();

52         y.pop();

53         //生成当前节点的四个子节点

54         for(i=0;i<4;i++){

55             nextx = prex + dx[i];

56             nexty = prey + dy[i];

57             if(nextx==outx&&nexty==outy){

58                 //如果新坐标为终点坐标

59                 return(step[prex][prey]+1);

60             }

61             if(nextx>0&&nextx<=12&&nexty>0&&nexty<=12&&used[nextx][nexty]==0&&map[nextx][nexty]==0){

62                 x.push(nextx);

63                 y.push(nexty);

64                 used[nextx][nexty]=1;

65                 step[nextx][nexty]=step[prex][prey]+1;

66             }

67         }

68     }

69     return 0;

70 }

巴特西

noj->电子老鼠走迷宫

00 问题

01 思路

01-1 类型

01-2 算法

02 代码

最新文章

热门文章