本文主要是介绍1042 电子老鼠闯迷宫，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
电子老鼠闯迷宫
时限：1000ms 内存限制：10000K 总时限：3000ms
描述：
有一只电子老鼠被困在如下图所示的迷宫中。这是一个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
#include<iostream>
#include<queue>using namespace std;int map[13][13];
int used[13][13]={0};
int step[13][13]={0};
int sx,sy,tx,ty,ux,uy,vx,vy;
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};void init();
int bfs();
queue<int>x;
queue<int>y;int main()
{int output;init();output=bfs();cout<<output<<endl;
} void init()
{int i,j;char temp; //注意temp为字符型变量cin>>sx>>sy>>tx>>ty;for(i=1;i<13;i++){for(j=1;j<13;j++){cin>>temp; //为了简化程序，将X转化成1，将.转化为0if(temp=='X'){map[i][j]=1;}else{map[i][j]=0;}}}x.push(sx);y.push(sy);used[sx][sy]=1;
}int bfs()
{int i;while(!x.empty()&&!y.empty()){ux=x.front();uy=y.front();x.pop();y.pop();for(i=0;i<4;i++){vx=ux+dx[i]; //找到新的坐标vy=uy+dy[i];if(vx==tx&&vy==ty) //如果新坐标恰好是目标{return(step[ux][uy]+1);}if(vx>0&&vx<=12&&vy>0&&vy<=12&&used[vx][vy]==0&&map[vx][vy]==0){x.push(vx);y.push(vy);used[vx][vy]=1;step[vx][vy]=step[ux][uy]+1;}}}
}
这篇关于1042 电子老鼠闯迷宫的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
