【1728 HDU】逃离迷宫（BFS）

今天药忘吃喽~ 2022-05-10 08:54 255阅读 0赞

题目：[点击打开题目链接][Link 1]

Problem Description：

给定一个m × n (m行, n列)的迷宫，迷宫中有两个位置，gloria想从迷宫的一个位置走到另外一个位置，当然迷宫中有些地方是空地，gloria可以穿越，有些地方是障碍，她必须绕行，从迷宫的一个位置，只能走到与它相邻的4个位置中,当然在行走过程中，gloria不能走到迷宫外面去。令人头痛的是，gloria是个没什么方向感的人，因此，她在行走过程中，不能转太多弯了，否则她会晕倒的。我们假定给定的两个位置都是空地，初始时，gloria所面向的方向未定，她可以选择4个方向的任何一个出发，而不算成一次转弯。gloria能从一个位置走到另外一个位置吗？

Input：

第1行为一个整数t (1 ≤ t ≤ 100),表示测试数据的个数，接下来为t组测试数据，每组测试数据中，  
　　第1行为两个整数m, n (1 ≤ m, n ≤ 100),分别表示迷宫的行数和列数，接下来m行，每行包括n个字符，其中字符'.'表示该位置为空地，字符'\*'表示该位置为障碍，输入数据中只有这两种字符，每组测试数据的最后一行为5个整数k, x1, y1, x2, y2 (1 ≤ k ≤ 10, 1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m),其中k表示gloria最多能转的弯数，(x1, y1), (x2, y2)表示两个位置，其中x1，x2对应列，y1, y2对应行。

Output：

每组测试数据对应为一行，若gloria能从一个位置走到另外一个位置，输出“yes”，否则输出“no”。

Sample Input：

2  
5 5  
...\*\*  
\*.\*\*.  
.....  
.....  
\*....  
1 1 1 1 3  
5 5  
...\*\*  
\*.\*\*.  
.....  
.....  
\*....  
2 1 1 1 3

Sample Output：

no  
yes

题目思路：这道题跟我们平时做的不太一样，平时都是用bfs套路求最少可以几步走到目的地，而这道题要求的是从起点到终点的最少拐弯次数，所以这道题按老套路是做不出来的。这里提供一种思路，因为要求拐弯次数，而如果你每走一步然后判断它是否拐弯，拐弯就+1，没有拐弯就不用加，的话比较麻烦，走一步判断一步，而且你必须要通过3个点才能判断它是否拐弯，即你要保留它上一步和它上上一步的坐标，才能判断它这一步是否拐弯，这样的话脑瓜子就比较容易晕，还不一定能判断对；那么问题来了，如何判断它是否拐弯了呢？你可以选定一个方向后，把这个方向走完（即把这个方向的点都遍历完，直到碰到障碍物为止），用一个二维数组标记每个位置，0代表这个位置的方向没有走过，1代表这个位置的方向已经走过了，不用管它的，所以当碰到0时，就说明拐弯了，此时的拐弯次数就是上一个方向的拐弯次数+1。（由于起点的时候方向未定，4个方向都不算拐弯，因此假设起点时的拐弯次数为-1）

下面举个栗子：（假设从S走到E，起点处的拐弯次数为-1，起初二维数组vis中都标记为0，还没开始走）

（为了方便，迷宫中未设置障碍物，起初的vis值我没有标）

1.从起点的4个方向开始，当碰到标记为0时，就说明这是个新的方向，此时拐弯次数就需要+1，走过之后就标记为1，则从起点开始的4个方向的拐弯次数为0，如图

![70][]

2.为了简便起见，假设第2个点是从S的右边第一个点，然后再从它开始对4个方向进行遍历，然后碰到0就将它的拐弯次数+1，标记过的地方就不用再遍历了，此时拐弯次数就变成了1，如图

![70 1][]

3.重复上述做法，直到找到答案为止。

MY DaiMa：

#include<iostream>
    #include<queue>
    #include<string.h>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    char flag[105][105];///迷宫里的字符
    int t, n, m, k, dir[4][2] = { {0,-1},{0,1},{-1,0},{1,0} };///t组测试样例，n行m列，dir4个方向
    int vis[105][105];///用来判断是否拐弯
    struct position
    {
        int x, y, time;///记录time拐弯次数
    } start, eend;
    int bfs()
    {
        queue<position> q;
        position cur,nex,rec;
        start.time = -1;
        flag[start.x][start.y] = '*';
        q.push(start);
        while(!q.empty())
        {
            cur = q.front();
            q.pop();
            if(cur.x == eend.x && cur.y == eend.y && cur.time <= k) return 1;
            for(int i = 0; i < 4 ;i++)
            {
                nex.x = cur.x + dir[i][0];
                nex.y = cur.y + dir[i][1];
                while((nex.x >= 0 && nex.x < n) && (nex.y >=0 && nex.y < m) && flag[nex.x][nex.y] != '*' )///将这个方向的点都遍历完
                {
                    if(vis[nex.x][nex.y] == 0)///未被标记过，说明这个方向是新的方向，此时拐弯次数需要+1
                    {
                        nex.time = cur.time + 1;
                        vis[nex.x][nex.y] = 1;///走过的地方标记
                        q.push(nex);
                    }
                    rec.x = nex.x + dir[i][0];///rec存的是这个方向的下一个点的坐标
                    rec.y = nex.y + dir[i][1];
                    nex = rec;
                }
            }
        }
        return -1;
    }
    int main()
    {
        int x1,x2,y1,y2;
        cin >> t;
        while(t--)
        {
            cin >> n >> m;
            for(int i = 0; i < n ;i ++)
            {
                for(int j = 0; j < m; j++)
                    cin >> flag[i][j];
            }
            cin >> k >> x1 >> y1 >> x2 >> y2;
            start.x = y1-1;
            start.y = x1-1;
            eend.x = y2-1;
            eend.y = x2-1;
            int ans;
            memset(vis,0,sizeof(vis));
            ans = bfs();
            if(ans == -1)
                cout << "no" << endl;
            else
                cout << "yes" << endl;
        }
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1728
[70]: /images/20220510/4f3d776244d24077aa592559f08bab18.png
[70 1]: /images/20220510/7f9c1919279f492084d1379f723c3584.png