描述：
有一只电子老鼠被困在如下图所示的迷宫中。这是一个12*12单元的正方形迷宫，黑色部分表示建筑物，白色部分是路。电子老鼠可以在路上向上、下、左、右行走，每一步走一个格子。现给定一个起点S和一个终点T，求出电子老鼠最少要几步从起点走到终点。
输入：
本题包含一个测例。在测例的第一行有四个由空格分隔的整数，分别表示起点的坐标S（x.y）和终点的坐标T（x,y）。从第二行开始的12行中，每行有12个字符，描述迷宫的情况，其中'X'表示建筑物，'.'表示路.
输出：
输出一个整数，即电子老鼠走出迷宫至少需要的步数。
输入样例：
2 9 11 8XXXXXXXXXXXXX......X.XXXX.X.XX.....XX.X.XX.XXX.XX.X.....X..XX.XXXXXXXXXXX...X.X....XX.XXX...XXXXX.....X....XXXX.XXXX.X.XXXXXXXX..XXXXXXXXXXXXXXX
输出样例：
28#include<queue>
#include<iostream>
#define N 12
using namespace std;
char map[N][N];
int mark[N][N];
int startX,startY,endX,endY;
int isCanMove(int x, int y, int& newX, int& newY, int direction) {
int tempX = x;
int tempY = y;
switch(direction) {
case 0:
tempX--;break;
case 1:
tempX++;break;
case 2:
tempY--;break;
case 3:
tempY++;break;
}
newX = tempX;
newY = tempY;
if(tempX < 0 || tempX >= N || tempY < 0 || tempY >= N) {
return 0;
}
if(map[tempX][tempY] == '.') {
return 1;
}
return 0;
}
int isUesed(int x, int y) {
if(mark[x][y] == 0) {
return 0;
}
return 1;
}
int isAim(int x, int y) {
if( x == (endX-1) && y == (endY-1)) {
return 1;
}
return 0;
}
int search(char map[N][N], int start_node) {
int x;
int y;
int newX;
int newY;
int num = 0;
queue<int> not_yet_explored;
not_yet_explored.push(start_node);
mark[startX - 1][startY - 1] = 1;
while(!not_yet_explored.empty()) {
int node_to_explored = not_yet_explored.front();
not_yet_explored.pop();
x = node_to_explored / N;
y = node_to_explored % N;
num = mark[x][y];
for(int i = 0;i < 4;i++) {
if(isCanMove(x, y, newX, newY, i)) {
if(isAim(newX, newY)) {
return num;
}
if(!isUesed(newX, newY)) {
mark[newX][newY] = num + 1;
not_yet_explored.push(newX*N + newY);
}
}
}
}
}
int main() {
cin >> startX >> startY >> endX >> endY;
for(int i = 0;i < N;i++) {
for(int j = 0;j < N;j++) {
cin >> map[i][j];
}
}
for(int row = 0;row < N;row++) {
for(int col = 0;col < N;col++) {
if(map[row][col] == '.') {
mark[row][col] = 0;
} else {
mark[row][col] = -2;
}
}
}
cout << search(map, (startX-1)*N + startY-1) << endl;
return 0;
}
本文摘自: 编程十万个为什么(http://www.bcwhy.com) 详细出处请参考：http://www.bcwhy.com/thread-1298-1-1.html
