AT2375 [AGC014C] Closed Rooms 题解

听取MLE声一片 · 2022-07-29 21:03:32 · 题解

注意是先移动再清。

容易想到的，我们可以从起点走到一个位置，然后朝一个方向解锁，之后朝着那个方向一直冲过去即可。而且第一次走是不能解锁的。

题目转化为在 k 步之内移动使得其距离边界最小并求出最小值。

我们从起点开始 bfs，保证到起点距离不超过 k，每移动一次更新一次最小值。

答案显然是最小距离需要走多少步再加上 1，注意要向上取整。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int N=810;
int n,m,k,x,y,xx[4]={-1,1,0,0},yy[4]={0,0,-1,1},len=1e9,vis[N][N];
char a[N][N];
void find(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j]=='S'){
                x=i;
                y=j;
                return;
            }
}
struct point{
    int x,y,s;
};
void bfs(){
    queue<point>q;
    q.push({x,y,0});
    vis[x][y]=1;
    while(!q.empty()){
        point p=q.front();
        q.pop();
        int res=min(min((p.x-1),(n-p.x)),min((p.y-1),(m-p.y)));
        len=min(len,res);
        if(p.s==k)
            continue;
        for(int i=0;i<4;i++){
            int tx=p.x+xx[i],ty=p.y+yy[i];
            if(a[tx][ty]!='.'||vis[tx][ty])
                continue;
            vis[tx][ty]=1;
            q.push({tx,ty,p.s+1});
        }
    }
}
int main()
{
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;i++)
        scanf("%s",a[i]+1);
    find();
    bfs();
    int ans=1+(len+k-1)/k;
    cout<<ans;
    return 0;
}