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
输出样例：
28
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 }