Description
定义一个二维数组：
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
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)
找最短路挺好找，还原有点恶心了
1 #include <algorithm> 2 #include <iostream> 3 #include <string> 4 #include <cstring> 5 #include <queue> 6 using namespace std; 7 typedef long long ll; 8 int a[5][5]; 9 const int INF=0x3f3f3f3f; 10 int dx[4]={0,0,1,-1}; 11 int dy[4]={1,-1,0,0}; 12 int d[5][5]; 13 int sx,sy,gx,gy,nx,ny; 14 int res; 15 struct node 16 { 17 int x,y; 18 int prex,prey; 19 }path[5][5],tmp; 20 void bfs() 21 { 22 queue<node> q; 23 for(int i=0;i<5;i++){ 24 for(int j=0;j<5;j++){ 25 d[i][j]=INF; 26 } 27 } 28 path[sx][sy].x=sx; 29 path[sy][sy].y=sy; 30 q.push(path[sx][sy]); 31 d[sx][sy]=0; 32 while(q.size()){ 33 node p=q.front(),q.pop(); 34 if(p.x==gx&&p.y==gy) break; 35 for(int i=0;i<4;i++){ 36 nx=p.x+dx[i],ny=p.y+dy[i]; 37 if(nx>=0&&nx<5&&ny>=0&&ny<5&&a[nx][ny]==0&&d[nx][ny]==INF){ 38 d[nx][ny]=d[p.x][p.y]+1; 39 path[nx][ny].prex=p.x; 40 path[nx][ny].prey=p.y; 41 path[nx][ny].x=nx; 42 path[nx][ny].y=ny; 43 q.push(path[nx][ny]); 44 } 45 } 46 } 47 res=d[gx][gy]; 48 } 49 void print_path(int x,int y) 50 { 51 if(x==0&&y==0){ 52 cout<<"("<<path[0][0].x<<", "<<path[0][0].y<<")"<<endl; 53 return ; 54 } 55 nx=path[x][y].prex; 56 ny=path[x][y].prey; 57 print_path(nx,ny); 58 cout<<"("<<path[x][y].x<<", "<<path[x][y].y<<")"<<endl; 59 } 60 int main() 61 { 62 for(int i=0;i<5;i++){ 63 for(int j=0;j<5;j++){ 64 cin>>a[i][j]; 65 } 66 } 67 sx=0,sy=0,gx=4,gy=4; 68 bfs(); 69 print_path(4,4); 70 return 0; 71 }
理解后自行敲一遍求总长的：
1 #include <iostream> 2 #include <string> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 #include <stack> 7 using namespace std; 8 typedef long long ll; 9 typedef pair<int,int> P; 10 const int INF=0x3f3f3f3f; 11 int dx[4]={0,0,1,-1}; 12 int dy[4]={1,-1,0,0}; 13 int a[5][5]; 14 int sx,sy,gx,gy,nx,ny; 15 int d[5][5]; 16 int res; 17 int bfs() 18 { 19 queue<P> que; 20 //P tmp; tmp.first=sx; tmp.second=sy; que.push(tmp); 21 que.push(P(sx,sy));//与上面的等价 22 //for(int i=0;i<5;i++){ 23 // for(int j=0;j<5;j++){ 24 // d[i][j]=INF; 25 // } 26 //} 27 memset(d,INF,sizeof(d));//与上面的等价 const int INF=0x3f3f3f3f; 28 //memset(d,0x3f3f,sizeof(d));//与上面的等价 29 sx=0,sy=0,gx=4,gy=4;//设置起点终点 30 d[sx][sy]=0; 31 while(que.size()){ 32 P q=que.front(); 33 que.pop(); 34 if(q.first==gx&&q.second==gy){ 35 return d[gx][gy];//到终点停止循环并返回总长 36 } 37 for(int i=0;i<4;i++){ 38 nx=q.first+dx[i],ny=q.second+dy[i]; 39 if(nx>=0&&nx<5&&ny>=0&&ny<5&&a[nx][ny]==0&&d[nx][ny]==INF){ 40 d[nx][ny]=d[q.first][q.second]+1; 41 que.push(P(nx,ny)); 42 } 43 } 44 } 45 } 46 int main() 47 { 48 for(int i=0;i<5;i++){ 49 for(int j=0;j<5;j++){ 50 cin>>a[i][j]; 51 } 52 } 53 cout<<bfs()<<endl;//输出最短的路径总长 54 return 0; 55 }