迷宫问题（BFS ➕输出路径）

冷不防 2021-12-03 23:23 344阅读 0赞

题目链接：[http://poj.org/problem?id=3984][http_poj.org_problem_id_3984]

思路：

这道题的难点我觉得主要是在记录路径上面。

我们不能去记录当前的步数的走的坐标（x，y） ，因为这样会被后面的覆盖。 所以我们记录的应该是前一步所走的

具体代码：

1 #include <iostream>
     2 #include <string>
     3 #include <cstring>
     4 #include <queue>
     5 #include <string.h>
     6 #include <stdio.h>
     7 #include <vector>
     8 
     9 using namespace std;
    10 
    11 typedef struct Node{
    12     int x;
    13     int y;
    14     int step;
    15 }Node;
    16 
    17 int ss[30][30];
    18 int map[5][5];
    19 int mx[4] = {
        1,-1,0,0};
    20 int my[4] = {
        0,0,-1,1};
    21 int vis[30][30];
    22 
    23 void bfs()
    24 {
    25     Node node;
    26     queue<Node> q;
    27     node.x = 0;
    28     node.y = 0;
    29     node.step = 0;
    30    // cnt = node.step;
    31    // ss[0][0]= 0;
    32    // ss[0][1]= 0;
    33     vis[0][0] = 1;
    34     q.push(node);
    35     while (!q.empty())
    36     {
    37         Node cur = q.front();
    38         q.pop();
    39         if (cur.x == 4 && cur.y == 4 )
    40         {
    41             for (int i=1;i<=cur.step;i++)
    42             {
    43                 int wx = ss[i][0];
    44                 int wy = ss[i][1];
    45                 printf("(%d, %d)\n",wx,wy);
    46             }
    47             printf("(4, 4)");
    48             return ;
    49         }
    50         for (int i=0;i<4;i++)
    51         {
    52             Node next = cur;
    53             int nx = next.x + mx[i];
    54             int ny = next.y + my[i];
    55             if (nx>=0&&ny>=0&&nx<5&&ny<5&&(!vis[nx][ny])&&map[nx][ny] == 0)
    56             {
    57                 next.x = nx;
    58                 next.y = ny;
    59                 vis[nx][ny] = 1;
    60                 next.step++;
    61         //        cnt = node.step;
    62                 ss[next.step][0]=cur.x;
    63                 ss[next.step][1]=cur.y;
    64                 q.push(next);
    65             }
    66         }
    67     }
    68 }
    69 
    70 
    71 
    72 int main()
    73 {
    74     for (int i=0;i<5;i++)
    75     {
    76         for (int j=0;j<5;j++)
    77             cin >> map[i][j];
    78     }
    79     memset(vis,0, sizeof(vis));
    80     bfs();
    81     return 0;
    82 }

转载于:https://www.cnblogs.com/-Ackerman/p/11186599.html

[http_poj.org_problem_id_3984]: http://poj.org/problem?id=3984