定义一个二维数组：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径，格式如样例所示。
Sample Input
0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
Sample Output
(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)
【思路】 结构体加string ,用来记录移动方向
#include<cstdio>
#include<string>
#include<string.h>
#include<queue>
#include<iostream>
using namespace std;
const int N=6;
int s[N][N],vis[N][N];
int e=5;
int dir[4][2]={0,-1,1,0,-1,0,0,1};
//D R L U 记录移动方向
struct node{
int x,y,step;
string pas;
}now,nex;
bool check(int x,int y){
if(s[x][y]==0&&x>0&&x<6&&y>0&&y<6&&!vis[x][y]){
vis[x][y]=1;
return true;
}
return false;
}
void prt(string t){//打印路径
int len=t.length() ;
int x=0 ,y=0 ;
cout<<"(0, 0)"<<endl;
for(int i=0;i<len;++i){
switch( t[i]){
case 'D':{
printf("(%d, %d)\n",x,y-1);
y--;
break;
}
case 'R':{
printf("(%d, %d)\n",x+1,y);
x++;
break;
}
case 'L':{
printf("(%d, %d)\n",x-1,y);
x--;
break;
}
default:{
printf("(%d, %d)\n",x,y+1);
y++;
break;
}
}
}
}
void bfs(){
queue<node>que;
while(!que.empty()) que.pop();
now.step =0,now.x =1,now.y =1,now.pas ="";
que.push(now);
while(!que.empty()){
nex=que.front();
que.pop();
if(nex.x ==5&&nex.y ==5){
prt(nex.pas );
}
for(int i=0;i<4;++i){
int dx=nex.x +dir[i][0],dy=nex.y +dir[i][1];
now.step =nex.step +1;
now.x =dx;
now.y =dy;
switch(i){
case 0:{;
if(check(dx,dy)){
now.pas =nex.pas +'D';
que.push(now);
}
break;
}
case 1:{
if(check(dx,dy)){
now.pas =nex.pas +'R';
que.push(now);
}
break;
}
case 2:{
if(check(dx,dy)){
now.pas =nex.pas +'L';
que.push(now);
}
break;
}
default:{
if(check(dx,dy)){
now.pas =nex.pas +'U';
que.push(now);
}
break;
}
}
}
}
}
int main(){
for(int i=1;i<=5;++i){
for(int j=1;j<=5;++j){
scanf("%d",&s[i][j]);
}
}
bfs();
return 0;
}