题目：
定义一个二维数组：
它表示一个迷宫，其中的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)
思路：BFS，每个点用string记录到达的路径
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>typedef long long ll;using namespace std;int maze[5][5];
int dir[4][2] = {
{0,1},{0,-1},{1,0},{-1,0}}; //方向数组
bool vis[5][5]; //标记位置是否已经被访问过 struct node{int i,j;string path; //记录到达该点的路径
};int main(){ios::sync_with_stdio(false);for(int i = 0 ; i<5 ; i++){for(int j = 0 ; j<5 ; j++){cin>>maze[i][j];}} queue<node> q;node t;node nxt;t.i = t.j = 0;t.path = ""; //初始时（0，0）位置路径为空 vis[0][0] = 1;q.push(t);while(1){t = q.front();q.pop();if(t.i==4 && t.j==4){ //若走到（4，4）点，根据保留的路径string输出走的过程点 int len = t.path.size();int a = 0;int b = 0;printf("(%d, %d)\n",a,b);for(int i = 0 ; i<len ; i++){if(t.path[i]=='0'){b += 1;printf("(%d, %d)\n",a,b);}else if(t.path[i]=='1'){b -= 1;printf("(%d, %d)\n",a,b);}else if(t.path[i]=='2'){a += 1;printf("(%d, %d)\n",a,b);}else if(t.path[i]=='3'){a -= 1;printf("(%d, %d)\n",a,b);}}return 9;} for(int i = 0 ; i<4 ; i++){if(t.i+dir[i][0]<=4 && t.i+dir[i][0]>=0 && t.j+dir[i][1]<=4 && t.j+dir[i][1]>=0 //在i方向上如果走一步不会走出maze && !maze[t.i+dir[i][0]][t.j+dir[i][1]] && !vis[t.i+dir[i][0]][t.j+dir[i][1]]){ //在i方向上走一步的话即将到达的点不是墙，且未被走到过 nxt.i = t.i+dir[i][0];nxt.j = t.j+dir[i][1];char k = '0'+i; nxt.path = t.path + k; //更新走到nxt点的路径 vis[nxt.i][nxt.j] = 1;q.push(nxt);}} }return 0;
}