P8693 [蓝桥杯 2019 国 AC] 大胖子走迷宫 题解

· · 题解

简要题意

占地 5 \times 5 的小明从 n \times n 的迷宫的 (3, 3) 走到 (n-2, n-2)。并且当到达时刻 k 的时候小明占地变成 3 \times 3，在时刻 2 \times k 的时候占地变成 1 \times 1。小明每次可以选择向上下左右四个方向走动，每次走动用时 1 个时刻，当然也可以选择站着不动。

求小明到达终点时的时刻。

思路

类似于求最短路径的问题，可以使用 bfs 讨论。

定义队列 q，含有四个元素：

每次取出队首并向四个方向以及不动拓展，并判断当前位置是否走过以及这个位置小明能否站的下（小明的占地区域内有没有障碍物），如果站的下就入队，入队时判断一下小明身材的情况。

判断的时候有个小优化，及当小明占地是 1 \times 1 的时候可以不用判断小明原地不动的情况，此时站着不动是无意义的举措，因为无论怎样走都不会有障碍物遮挡他。

代码

#include <bits/stdc++.h>
#define ll long long
#define setp setprecision
#define mem(a, m) memset(a, m, sizeof(a));
using namespace std;

int n, k;
int ans = 0x3f3f3f;
int a[305][305];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool vis[305][305];
struct node {
    int x, y;//坐标
    int Time;//时间
    int size;//小明大小 
};
bool check(int x, int y, int size)
{
    if(vis[x][y])   return false;
    for(int i=x-size;i<=x+size;i++)
        for(int j=y-size;j<=y+size;j++)
            if(i < 1 || i > n || j < 1 || j > n || a[i][j])
                return false;
    return true;
}
int work(int Time)
{
    if(Time < k)    return 2;
    else if(Time < 2 * k)   return 1;
    else    return 0;
}
void bfs()
{
    queue <node> q;
    vis[3][3] = 1;
    q.push((node){3, 3, 0, 2});
    while(!q.empty())
    {
        node t = q.front();
        q.pop();
        if(t.x == n - 2 && t.y == n - 2)//到达终点，停止搜索 
        {
            cout << t.Time;
            return ;
        }
        if(t.size != 0) q.push((node){t.x, t.y, t.Time+1, work(t.Time+1)});//站着不动
        for(int i=0;i<4;i++)
        {
            int X = t.x + dx[i];
            int Y = t.y + dy[i];
            if(check(X, Y, t.size))//判断
            {
                vis[X][Y] = 1;
                q.push((node){X, Y, t.Time+1, work(t.Time+1)});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            char c;
            cin >> c;
            if(c == '*')    a[i][j] = 1;
            else    a[i][j] = 0;
        }
    }
    bfs();
    return 0;
}