在线评测传送门:AcWing 2548. 大胖子走迷宫

思路

这题就是一个简单的bfs。

要注意的细节就是每次先判断按照原长度走能不能到下一个点,然后再更新长度。

最多访问n^2^个点,最多等待k次,时间复杂度$O(n^2+k)$。

小优化:当时间>=2*k,就会变成1*1大小,就可以不用再原地等待了;其余情况都要把原地等待的状态入队。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=310;
char s[N][N];
int n,k;
int dir[4][2]={0,1,0,-1,1,0,-1,0}; // 右、左、下、上
bool vis[N][N];
struct node
{
    int x,y,cnt,len; // len表示长度,初始为2
};
bool judge(int x,int y,int len) // 用原长度判断能否到达(x,y)
{
    if(vis[x][y]||y+len>n||y-len<1||x+len>n||x-len<1)return 0;
    for(int i=x-len;i<=x+len;i++)
        for(int j=y-len;j<=y+len;j++)
            if(s[i][j]=='*')return 0;
    return 1;
}
int f(int cnt) // 由时间计算对应长度 
{
    int len;
    if(cnt<k)len=2;
    else if(cnt<2*k)len=1;
    else len=0;
    return len;
}
int bfs()
{
    queue<node>q;
    q.push({3,3,0,2});
    vis[3][3]=1;
    while(q.size())
    {
        node tmp=q.front();q.pop();
        int x=tmp.x;
        int y=tmp.y;
        int cnt=tmp.cnt;
        int len=tmp.len;
        //printf("x=%d y=%d cnt=%d len=%d\n",x,y,cnt,len);
        if(x==n-2&&y==n-2)return cnt;

        if(len!=0) // 现在还没变成1*1,原地等待
        {
            q.push({x,y,cnt+1,f(cnt+1)}); 
        }

        for(int i=0;i<4;i++)
        {
            int nx=x+dir[i][0];
            int ny=y+dir[i][1];
            if(judge(nx,ny,len)) // 判断新点(nx,ny)在原长度时能否移动 
            {
                vis[nx][ny]=1;
                q.push({nx,ny,cnt+1,f(cnt+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++)
            cin>>s[i]+1;
    int ans=bfs();
    printf("%d\n",ans);
    return 0;
}
/*
9 5
+++++++++
+++++++++
+++++++++
+++++++++
+++++++++
***+*****
+++++++++
+++++++++
+++++++++
ans:16

15 21
+++++**********
++++++++*******
++++++++**+++**
+++++++++++++**
+++++++++++++**
++++++++++*****
++++++++++*****
**++++++++++***
**+++++++++++++
**+++++++++++++
+++++++++++++++
+++++++++++++++
+++++**++++++++
+++++*****+++++
+++++*****+++++
ans:20
*/