题意
中文题，求最短路并且输出路径。
思路
求最短路理所应当BFS，但是关键在于输出路径，输出路径又是通过回溯，关键在于怎么写，写法好多种。
由于该题数据小，所以还可以，通过DFS不断回溯输出路径。
AC代码
#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; #define sc(T) scanf("%d",&T) #define scc(x,y) scanf("%d %d",&x,&y) #define pr(T) printf("%d\n",T) #define f(a,b,c) for (int a=b;a<=c;a++) #define ff(a,b,c) for (int a=b;a>=c;a--) #define inf 0x3f3f3f3f #define mem(a,b) memset(a,b,sizeof(a)) #define eps 1e-9 #define PI acos(-1) int a[7][7]; bool book[7][7]; int to[4][2]={{1, 0},{-1,0},{0, 1},{0, -1}}; struct node { int x,y; // int pre; // 前驱 node(int xx=0,int yy=0) { x=xx; y=yy; } }pre[7][7]; void dfs(int x,int y) { // if(Q[x].pre!=-1) // { // dfs(b[x].pre); // printf("(%d, %d)\n",b[x].x,b[x].y); // } if(x==0&&y==0) { printf("(0, 0)\n"); return; } node t=pre[x][y]; dfs(t.x,t.y); printf("(%d, %d)\n",x,y); } void bfs() { queue Q; node p,q; // p.x=0,p.y=0,p.pre=1; book[0][0]=1; //Q.push(p); Q.push(node(0,0));//上面加三行代码 while(!Q.empty()) { q=Q.front(); Q.pop(); if(q.x==4&&q.y==4) return; for(int i=0;i<4;i++) { p=q; p.x+=to[i][0]; p.y+=to[i][1]; if(p.x>=0&&p.x<5&&p.y>=0&&p.y<5&&a[p.x][p.y]==0&&!book[p.x][p.y]) { book[p.x][p.y]=1; //p.pre= //Q.push(p); pre[p.x][p.y]=q; Q.push(p); } // if(p.x==4&&p.y==4) // dfs(); } } } int main() { for(int i=0;i<5;i++) { for(int j=0;j<5;j++) sc(a[i][j]); } // s.x=0,s.y=0,t.x=4,t.y=4; // bfs(); //printf("(0, 0)\n"); bfs(); dfs(4,4); //printf("(4, 4)\n"); return 0; }