题解：AT_agc014_c [AGC014C] Closed Rooms

CQ_Bab · 2024-08-17 17:18:14 · 题解

前言

该长脑子了。

思路

首先我们可以分析题面发现一次最多走 k 次二最多也能开 k 个锁所以我们考虑将每一次开锁弄到走之前这也很简单，先提前走一次即可，因为这样做可以保证以后走的路都畅通无阻，那么对于第一次直接暴搜即可，然后求出每一个点到四面的最短距离，假如为 res，那么答案就是 \lceil \frac{res}{k} \rceil+1 因为要加上第一轮。

代码

关于深搜啊，他死掉了，还是写广搜吧。

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define in(x) scanf("%lld",&x)
#define int long long
#define fire signed
#define il inline
il void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) print(x/10);
    putchar(x%10+'0');
}
int T=1;
int n,m,k;
const int N=810;
char c[N][N];
int tx[]={0,-1,0,1};
int ty[]={-1,0,1,0};
int qx,qy,res=INT_MAX;
int vis[N][N];
struct node{
    int x,y,s;
};
queue<node>q;
void bfs() {
    while(q.size()) {
        node s=q.front();
        q.pop();
        int x=s.x,y=s.y,z=s.s;
        if(z>k) continue;
        res=min(res,min(min(x-1,y-1),min(n-x,m-y)));
        vis[x][y]=1;
        rep(i,0,3) {
            int dx=x+tx[i],dy=y+ty[i];
            if(dx<1||dy<1||dx>n||dy>m||c[dx][dy]=='#'||vis[dx][dy]) continue;
            vis[dx][dy]=1;
            q.push({dx,dy,z+1});
        }
    }
}
void solve() {
    in(n),in(m),in(k);
    rep(i,1,n) rep(j,1,m) {
        cin>>c[i][j];
        if(c[i][j]=='S') qx=i,qy=j;
    }
    q.push({qx,qy,0});
    bfs();
    cout<<(res+k-1)/k+1<<endl;
}
fire main() {
    while(T--) {
        solve();
    }
    return false;
}