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

· · 题解

题目大意

一张 n\times n 的地图，一个大胖子，一开始占用 5\times 5 的区域，从 0 时刻出发，可以向上、下、左、右四个方向走，在时刻 k 会变成一个胖子，只占用 3\times3 的区域，在时刻 2\times k 会变成一个正常人，只占用 1\times1 的区域。

问从起点第 3 行第 3 列到终点第 n-2 行第 n-2 列的最少时间

题目解析

很明显这是一题最短路，用广搜即可。

int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
struct node{int x,y,t;};
void bfs()
{
    int vis[305][305];
    int xx,yy;
    queue<node>q;
    node f;
    q.push((node){3,3,0});
    vis[3][3]=1;
    for(int i=2;i>=0;i--)
        while(!q[i].empty())
        {
            f=q.front();
            q.pop();
            if(f.x==n-2&&f.y==n-2)
            {
                cout<<f.t;
                return ;
            }
            for(int j=0;j<4;j++)
            {
                xx=f.x+dx[j];
                yy=f.y+dy[j];
                //……
            }
        }
}

这是大致模板，结构体中的 x，y 表示位置 t 表示时间。

但题目中的人却有三个不同状态。

所也就可用三个队列实现，分别为 p_0，p_1，p_2 分别搜索占用 1\times1，3\times3，5\times 5 区域可以走到的位置

从 p_2 开始搜索，题目中说可以在原地等待，所以每搜到一个位置，都可以原地等直到变为下一个状态，所以每个位置都可以把时间变为 k 或 2\times k 再进到下一个队列即可。

接着就是判断是否出界和是否可以通过。

前面我们让 p_0，p_1，p_2 分别来搜索占用 1\times1，3\times3，5\times 5 区域可以走到的位置，所以队列的下标很方便地可以帮助我们判断是否出界和是否可以通过，具体如下：

5=2\times2+1 3=2\times1+1 1=2\times0+1

如果下标为 i,则只要看这个位置周围 i 的范围即可

其次可用前缀和优化来优化判断是否可以通过，代码如下：

for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>c;
            if(c=='*')
                a[i][j]=1;
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        }
sum=s[xx+i][yy+i]-s[xx+i][yy-i-1]-s[xx-i-1][yy+i]+s[xx-i-1][yy-i-1];
if(xx<1+i||xx>n-i||yy<1+i||yy>n-i||vis[xx][yy]==1||sum!=0)
    continue;

最终代码

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[305][305],s[305][305];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
char c;
struct node{int x,y,t;};
void bfs()
{
    int vis[305][305];
    int xx,yy,sum;
    queue<node>q[3];
    node f;
    q[2].push((node){3,3,0});
    vis[3][3]=1;
    for(int i=2;i>=0;i--)//枚举每个队列（状态）
        while(!q[i].empty())
        {
            f=q[i].front();
            q[i].pop();
            if(f.x==n-2&&f.y==n-2)
            {
                cout<<f.t;
                return ;
            }
            for(int j=0;j<4;j++)
            {
                xx=f.x+dx[j];
                yy=f.y+dy[j];
                sum=s[xx+i][yy+i]-s[xx+i][yy-i-1]-s[xx-i-1][yy+i]+s[xx-i-1][yy-i-1];
                if(xx<1+i||xx>n-i||yy<1+i||yy>n-i||vis[xx][yy]==1||sum!=0)
                    continue;
                vis[xx][yy]=1;
                q[i].push((node){xx,yy,f.t+1});
            }
            if(f.t<(3-i)*k&&i>0)
                q[i-1].push((node){f.x,f.y,(3-i)*k});//时间如果没到下一个可以变瘦的时间，则可以原地等待到变瘦
        }
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>c;
            if(c=='*')
                a[i][j]=1;
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];//前缀和优化
        }
    bfs();
    return 0;
}