嗯...

 

题目链接：

 

这道题属于bfs + 记录路径，在bfs的模板上需要有些更改：

bfs求最短路径有一个优点就是求出来的第一条路径就是最短路径，这与bfs的性质有关...

首先要记录路径的长度，然后要记录每次决策的方向...最后输出时从起点开始将记录下来的决策走一遍然后接着输出即可...

 

AC代码：

1 #include
      
        2 #include
       
         3 #include
        
          4  5 using namespace std; 6  7 struct node{ 8     int x, y; 9     int s;//路径长度10     int l[50];//每次决策11 };12 13 int g[10][10], vis[10][10];14 int dir[4][2] = {
    {-1, 0}, {
    1, 0}, {
    0, 1}, {
    0, -1}};15 16 inline node bfs(){17     queue
         
           q;18     node now, next;19     now.x = 0;20     now.y = 0;21     now.s = 0;22     vis[0][0] = 1;23     q.push(now);24     while(!q.empty()){25         now = q.front();26         q.pop();27         if(now.x == 4 && now.y == 4) return now;28         for(int i = 0; i < 4; i++){29             next.x = now.x + dir[i][0];30             next.y = now.y + dir[i][1];31             if(next.x >= 0 && next.x <= 4 && next.y >= 0 && next.y <= 4 && !g[next.x][next.y] && !vis[next.x][next.y]){32                 next.s = now.s + 1;33                 next.l[now.s] = i;34                 vis[next.x][next.y] = 1;35                 q.push(next);36             }37         }38     }39     return now;40 }41 42 int main(){43     for(int i = 0; i < 5; i++){44         for(int j = 0; j < 5; j++){45             scanf("%d", &g[i][j]);46         }47     }48     node ans = bfs();49     int x = 0, y = 0;50     printf("(0, 0)\n");51     for(int i = 0; i < ans.s; i++){52         x += dir[ans.l[i]][0];53         y += dir[ans.l[i]][1];54         printf("(%d, %d)\n", x, y);55     }//根据记录的决策输出56     return 0;57 }