• 5 h0255. 迷宫问题，6 h0253. 鸣人和佐助（广度优先搜索）

    5 h0255. 迷宫问题

    给定一个 n×n 的二维数组，如下所示：

    1. int maze[5][5] = {
    2.                     0, 1, 0, 0, 0,
    3.                     0, 1, 0, 1, 0,
    4.                     0, 0, 0, 0, 0,
    5.                     0, 1, 1, 1, 0,
    6.                     0, 0, 0, 1, 0,
    7. };

    它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

    数据保证至少存在一条从左上角走到右下角的路径。

    输入格式:

    第一行包含整数 n（0≤n≤1000）。

    接下来 n 行，每行包含 n 个整数 0 或 1，表示迷宫。

    输出格式:

    输出从左上角到右下角的最短路线，如果答案不唯一，输出任意一条路径均可。

    按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 (0,0)，右下角坐标为 (n−1,n−1)。

    输入样例:

    1. 5
    2. 0 1 0 0 0
    3. 0 1 0 1 0
    4. 0 0 0 0 0
    5. 0 1 1 1 0
    6. 0 0 0 1 0

    输出样例:

    1. 0 0
    2. 1 0
    3. 2 0
    4. 2 1
    5. 2 2
    6. 2 3
    7. 2 4
    8. 3 4
    9. 4 4

    代码长度限制

    16 KB

    时间限制

    400 ms

    内存限制

    64 MB

     代码：

            一开始用递归写的广搜，测试点通不过，问老师说递归不需要广搜哈哈，就改成不用递归的广搜了哈哈。

    不带递归的广搜：

    1. #include
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8.  
    9. const int Max = 1010;
    10.  
    11. using namespace std;
    12.  
    13. //结点结构
    14. typedef struct Point
    15. {
    16.     int x, y;
    17. }point;
    18.  
    19. //地图
    20. int maze[Max][Max];
    21. point path[Max][Max];  //走过的路径，每个位置记录他的父位置
    22. int visitied[Max][Max] = {0}; //看结点是否经过
    23.  
    24. int n;
    25.  
    26.  
    27.  
    28. //上下左右移动的数组,上下左右的顺序
    29. int xMove[4] = {-1, 1, 0, 0};
    30. int yMove[4] = { 0, 0,-1, 1};
    31.  
    32.  
    33. point start; // 起点的位置
    34. point endp;  //终点的位置
    35.  
    36. void bfs();
    37. void show();
    38. void showPath();
    39.  
    40. int main()
    41. {
    42.     //迷宫大小为n
    43.     cin >> n ;
    44.  
    45.     //初始化迷宫、起点和中点，包一圈围墙好判断
    46.     memset(maze, 1, sizeof(maze));
    47.     start.x = 1; start.y = 1;
    48.     endp.x = n; endp.y = n;
    49.  
    50.     //输入地图
    51.     for(int i = 1; i <= n; i++)
    52.         for(int j = 1; j <= n; j++)
    53.             cin >> maze[i][j];
    54.  
    55.  
    56.     //bfs解决问题
    57.  
    58.     visitied[1][1] = 1; //起始点设为走过
    59.     path[1][1].x = -1; path[1][1].y = -1; //设出发点的父结点为-1，-1，用来做输出的停止
    60.     bfs();
    61.     show();
    62.     //showPath();  //测试路径数组
    63.  
    64.     return 0;
    65. }
    66.  
    67. void bfs()
    68. {
    69.     queue q;  //存放能走的路，遍历完四个方向后出队
    70.     point next; //下一个结点
    71.     q.push(start); //将第一个结点范进队列
    72.  
    73.     //遍历所有队列的元素
    74.     while(!q.empty())
    75.     {
    76.         for(int i = 0; i < 4; i++)
    77.         {
    78.             //设置下一个结点
    79.             //cout<< "当前判断的是" << q.front().x << ' ' << q.front().y << "位置" << endl;
    80.             next.x = q.front().x + xMove[i];
    81.             next.y = q.front().y + yMove[i];
    82.  
    83.  
    84.             //如果是0，并且没走过，入队
    85.             if(maze[next.x][next.y] == 0 && visitied[next.x][next.y] == 0)
    86.             {
    87.                 //cout<< "结点：" << next.x << ' ' << next.y << "位置可以走" << endl;
    88.                 q.push(next);
    89.  
    90.                 visitied[next.x][next.y] = 1;
    91.                 //在路径path中，记录该节点的父元素位置
    92.                 path[next.x][next.y] = q.front();
    93.  
    94.             }
    95.  
    96.  
    97.         }
    98.  
    99.         q.pop();
    100.  
    101.         //cout << d.x << ' ' << d.y << ' ' << d.t << ' ' << d.time << endl;
    102.  
    103.     }
    104.  
    105. }
    106.  
    107. void show()
    108. {
    109.     //从迷宫终点往回找，并存进栈中
    110.     point now, next;
    111.     now.x = now.y = n;
    112.     stack s;
    113.     s.push(now);
    114.  
    115.     //now为起点时结束
    116.     while(path[now.x][now.y].x != -1 && path[now.x][now.y].y != -1)
    117.     {
    118.         next = path[now.x][now.y]; //在path中找下一个位置的坐标next
    119.         now = next;                //入栈
    120.         s.push(now);
    121.     }
    122.  
    123.     //输出
    124.     while(!s.empty())
    125.     {
    126.         now = s.top();
    127.  
    128.         cout << now.x-1 << ' ' << now.y-1 << endl;
    129.         s.pop();
    130.     }
    131. }
    132.  
    133. //测试路径
    134. void showPath()
    135. {
    136.     for(int i = 1 ;i <= n; i++)
    137.     {
    138.         for(int j = 1; j <= n; j++)
    139.         {
    140.             cout << '(' << path[i][j].x << ' ' << path[i][j].y << ')' << ' ';
    141.         }
    142.          cout << endl;
    143.     }
    144. }

    带递归的广搜：

    1. #include
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6.  
    7. /*思路：从起点出发，每次判断上下左右的是否为0（通路），是的话将该条通路放进队列，
    8. 将所有通路放进队列后，再依次判断每个通路的上下左右是否为0。
    9. */
    10.  
    11.  
    12.  
    13. using namespace std;
    14.  
    15. //每个位置的坐标和它的父结点在队列中的位置
    16. struct Point
    17. {
    18.     int x, y;
    19.     int f;
    20. };
    21. void bfs(Point s);  //广度优先遍历
    22. void show(Point q); //按照要求输出函数
    23. void show2();
    24.  
    25. int n;              //迷宫的行列
    26. int maze[1010][1010];//存放迷宫的二维数组
    27. int path = 0;
    28.  
    29. Point que[1000010];   //队列，存放可以走的通路值
    30. int head = 0;       //头指针
    31. int tail = 0;       //尾指针
    32.  
    33. Point resort[1000010]; //答案存放在这
    34.  
    35. int main()
    36. {
    37.     //按照要求输入
    38.     cin >> n;
    39.     if(n == 0)
    40.     {
    41.         cout << 0 << ' ' << 0 << endl;
    42.         return 0;
    43.     }
    44.     for(int i = 0; i <= n+1; i++)
    45.     {
    46.         for(int j = 0; j <= n+1; j++)
    47.         {
    48.             maze[i][j] = 1;
    49.         }
    50.     }
    51.  
    52.     for(int i = 1; i <= n; i++)
    53.     {
    54.         for(int j = 1; j <= n; j++)
    55.         {
    56.             cin >> maze[i][j];
    57.         }
    58.     }
    59.  
    60.     //定义一个位置，用来当起点
    61.     Point s;
    62.     s.f = -1; s.x = 1; s.y = 1;
    63.     //把起点先放进队列
    64.     que[tail++] = s;
    65.     //用起点来调用bfs算法
    66.     bfs(s);
    67.     //输出
    68.     show(que[tail-1]);
    69.     for(int i = path-1; i >= 0; i--)
    70.         cout << resort[i].x-1 << ' ' << resort[i].y-1 << endl;
    71.  
    72.     //测试用
    73.  /*   show2();
    75.     for(int i = 0; i <= n+1; i++)
    76.     {
    77.         for(int j = 0; j <= n+1; j++)
    78.         {
    79.             cout << maze[i][j] << ' ';
    80.         }
    81.         cout << endl;
    82.     }*/
    83. }
    84.  
    85. void bfs(Point s)
    86. {
    87.     Point q;    //用来存放每个改变的位置
    88.     q.f = head; //当前判断的数是头结点
    89.     maze[s.x][s.y] = 2; //该点设为走过
    90.     int count = 0;
    91.     //如果该点是终点，返回
    92.     if(s.x == n && s.y == n)
    93.     {
    94.         return;
    95.     }
    96.  
    97.     //如果上下左右的节点是0，放进队列，并且置该点为2
    98.     //上
    99.     q.x = s.x-1; q.y = s.y;
    100.     if(maze[q.x][q.y] == 0)
    101.     {
    102.         //cout << "上" << endl;
    103.         que[tail++] = q;
    104.         count++;
    105.     }
    106.     //下
    107.     q.x = s.x+1; q.y = s.y;
    108.     if(maze[q.x][q.y] == 0)
    109.     {
    110.         //cout << "下" << endl;
    111.         que[tail++] = q;
    112.         count++;
    113.     }
    114.     //左
    115.     q.x = s.x; q.y = s.y-1;
    116.     if(maze[q.x][q.y] == 0)
    117.     {
    118.         //cout << "左" << endl;
    119.         que[tail++] = q;
    120.         count++;
    121.     }
    122.     //右
    123.     q.x = s.x; q.y = s.y+1;
    124.     if(maze[q.x][q.y] == 0)
    125.     {
    126.         //cout << "右" << endl;
    127.         que[tail++] = q;
    128.         count++;
    129.     }
    130.     //cout << "----------------------------------" <
    131.     //再依次调用bfs
    132.     head++;
    133.     bfs(que[head]);
    134.  
    135. }
    136.  
    137. void show(Point q)
    138. {
    139.     while(q.f != -1)
    140.     {
    141.         //cout << q.x-1 << ' ' << q.y-1 << ' ' << endl;
    142.         resort[path++] = q;
    143.         q = que[q.f];
    144.  
    145.     }
    146.     if(q.f == -1)
    147.     {
    148.         //cout << q.x-1 << ' ' << q.y-1 << ' ' << endl;
    149.         resort[path++] = q;
    150.     }
    151.  
    152. }
    153.  
    154. void show2()
    155. {
    156.     for(int i = 0; i < tail; i++)
    157.     {
    158.         cout << i << ": " << que[i].x-1 << ' ' << que[i].y-1 << ' ' << que[i].f << endl;
    159.     }
    160. }

    6 h0253. 鸣人和佐助

    佐助被大蛇丸诱骗走了，鸣人在多少时间内能追上他呢？

    已知一张地图（以二维矩阵的形式表示）以及佐助和鸣人的位置。地图上的每个位置都可以走到，只不过有些位置上有大蛇丸的手下，需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉，每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动，每移动一个距离需要花费1个单位时间，打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了，则只可以走到没有大蛇丸手下的位置，不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动，大蛇丸的手下也不移动。请问，鸣人要追上佐助最少需要花费多少时间？

    输入格式:

    输入的第一行包含三个整数：M，N，T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200，0 ≤ T < 10
    后面是M行N列的地图，其中@代表鸣人，+代表佐助。*代表通路，#代表大蛇丸的手下。

    输出格式:

    输出包含一个整数R，代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助，则输出-1。

    输入样例1:

    1. 4 4 1
    2. #@##
    3. **##
    4. ###+
    5. ****

    输出样例1:

    6

    输入样例2:

    1. 4 4 2
    2. #@##
    3. **##
    4. ###+
    5. ****

    输出样例2:

    4

    代码长度限制

    16 KB

    时间限制

    400 ms

    内存限制

    64 MB

     代码：

            其实我是先做的这道题，然后用这道题的代码改成上一题的，话说鸣人的查克拉难道不是用不完的吗哈哈。

    1. #include
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7.  
    8. const int Max = 210;
    9.  
    10. using namespace std;
    11.  
    12. //结点结构
    13. typedef struct Point
    14. {
    15.     int x, y;
    16.     int t;  //查克拉
    17.     int time;  //花的时间
    18. }point;
    19.  
    20. //地图
    21. char maze[Max][Max];
    22. point path[Max][Max];  //走过的路径，每个位置记录他的父位置
    23. int visitied[Max][Max] = {0}; //看结点是否经过
    24.  
    25. int m, n, t;
    26.  
    27.  
    28.  
    29. //上下左右移动的数组,上下左右的顺序
    30. int xMove[4] = {-1, 1, 0, 0};
    31. int yMove[4] = { 0, 0,-1, 1};
    32.  
    33.  
    34. point mingRen; // 名人的位置
    35. point zuoZhu;  //佐助的位置
    36.  
    37. int bfs();
    38.  
    39. int main()
    40. {
    41.     //行m，列n，名人查克拉t
    42.     cin >> m >> n >> t;
    43.  
    44.     //初始化迷宫，包一圈围墙好判断
    45.     memset(maze, 0, sizeof(maze));
    46.     //初始化path，让没走过的为no
    47.  
    48.  
    49.     //其中@代表鸣人，+代表佐助。*代表通路，#代表大蛇丸的手下
    50.     for(int i = 1; i <= m; i++)
    51.         for(int j = 1; j <= n; j++)
    52.         {
    53.             cin >> maze[i][j];
    54.             //找到名人和佐助的位置
    55.             if(maze[i][j] == '@')
    56.             {
    57.                 mingRen.x = i;
    58.                 mingRen.y = j;
    59.             }
    60.             if(maze[i][j] == '+')
    61.             {
    62.                 zuoZhu.x = i;
    63.                 zuoZhu.y = j;
    64.             }
    65.         }
    66.  
    67.     //bfs解决问题
    68.     mingRen.t = t;  //名人的查克拉
    69.     mingRen.time = 0;//一开始的时间为0
    70.     visitied[mingRen.x][mingRen.y] = 1; //起始点设为走过
    71.     int resort = bfs();
    72.     cout << resort;
    73.     return 0;
    74. }
    75.  
    76. int bfs()
    77. {
    78.     queue q;  //存放能走的路，遍历完四个方向后出队
    79.     point next; //下一个结点
    80.     q.push(mingRen); //将第一个结点范进队列
    81.  
    82.     //遍历所有队列的元素
    83.     while(!q.empty())
    84.     {
    85.         for(int i = 0; i < 4; i++)
    86.         {
    87.             //设置下一个结点
    88.             next.x = q.front().x + xMove[i];
    89.             next.y = q.front().y + yMove[i];
    90.             next.t = q.front().t;
    91.             next.time = q.front().time;
    92.  
    93.             //如果是*，并且没走过，则不需要小号查克拉，直接入队
    94.             if(maze[next.x][next.y] == '*' && visitied[next.x][next.y] == 0)
    95.             {
    96.                 next.time++;
    97.                 q.push(next);
    98.                 //cout << next.x << ' ' << next.y << ' ' << next.t << ' ' << next.time << endl;
    99.                 visitied[next.x][next.y] = 1;
    100.                 //在路径path中，记录该节点的父元素位置
    101.                 path[next.x][next.y] = mingRen;
    102.  
    103.             }
    104.             //如果是#，大蛇丸手下,判断查克拉
    105.             else if(maze[next.x][next.y] == '#' && visitied[next.x][next.y] == 0)
    106.             {
    107.                 if(next.t > 0)
    108.                 {
    109.                     next.time++;
    110.                     //cout << " haha" << endl;
    111.                     next.t--;  //消耗一点查克拉
    112.                     q.push(next);
    113.                     //cout << next.x << ' ' << next.y << ' ' << next.t << ' ' << next.time << endl;
    114.                     visitied[next.x][next.y] = 1;
    115.                     //在路径path中，记录该节点的父元素位置
    116.                     path[next.x][next.y] = mingRen;
    117.                 }
    118.  
    119.             }
    120.             //如果是+，就是佐助，存入路径，结束调用
    121.             else if(maze[next.x][next.y] == '+')
    122.             {
    123.                 next.time++;
    124.                 q.push(next);
    125.                 path[next.x][next.y] = mingRen;
    126.                 return next.time;
    127.             }
    128.         }
    129.         point d = q.front();
    130.         q.pop();
    131.  
    132.         //cout << d.x << ' ' << d.y << ' ' << d.t << ' ' << d.time << endl;
    133.  
    134.     }
    135.     //到这说明到不了佐助
    136.     return -1;
    137.  
    138.  
    139. }

    若对您有帮助麻烦点个赞哦~

  • 相关阅读:
    惨，给Go提的代码被批麻了
    2. IDEA配置antlr4（on mac）
    深度学习硬件介绍
    Assert断言常用工具类
    bootstrap 主题
    并发编程之 ThreadLocal
    高级深入--day37
    在 Kubernetes 上部署 DM
    重庆开放大学学子们的好帮手
    LeetCode-62-不同路径-动态规划
  • 原文地址：https://blog.csdn.net/weixin_63484669/article/details/127693927