题解 P7151 【[USACO20DEC] Replication G】

· · 题解

性质1：在机器人不会碰到岩石的前提下，对于每一个点，我们尽量让初始的机器人直接经过这个点，而不是让副本覆盖到这个点。

证明：因为D\ge1，副本向外扩展的速度最多和初始的机器人移动的速度一样快。在合法的前提下，如果机器人能扩展到这个点，那么它一定能够经过这个点。

性质2：在使得经过的点最多的情况下，每个点最多只能经过一次。

证明：根据性质1，我们尽量让初始的机器人直接经过一个点。当我们第二次经过某个点时，相较于第一次到达时我们又多花费了一些时间，机器人要么在这段时间里进行复制，使得我们能够直接经过的点变少，要么虽然还没有复制，但是相较于第一次经过时离下一次复制的时间更近了。

上面两个性质是本题能够使用BFS求解的基础。

我们进行第一遍BFS，初始时向队列里加入每一个‘#’点，计算出每个点所能接受的机器人最多复制的次数，即每个点离它最近的‘#’的距离。

随后我们进行第二遍BFS，初始时向队列里加入每一个起点，尽可能的多经过点。

现在我们该统计答案了。我们如何快速计算出每个点？这也是本题最后一个难点。

对于每个目前我们已经经过的节点，我们将三元组(x,y,t)加入一个优先队列中，其中x,y是这个点的坐标，t是这个点最多能向外扩展多少步，优先队列按照t从大到小排序。每次我们取出优先队列的队头，然后向优先队列中加入(x,y-1,t-1)，(x,y+1,t-1)，(x-1,y,t-1)和(x+1,y,t-1)，并给这些点打上标记。最后我们统计所有被打上标记的点的个数，就是答案了。

为什么这么做是对的呢？考虑每一个点在上述过程中可能被扩展到多个合法的t值，显然t值最大的是最优的。通过t值从大到小排序，我们保证了每次的扩展都是最优的。

前两次BFS的复杂度是O(n^2)的，最后一次BFS中，每一个节点最多只会扩展一次。由于我们使用了一个有限队列，所以时间复杂度为O(n^2 \log n)。

总的时间复杂度为O(n^2 \log n)。

注意在本题中，是先扩展再复制，对于这种细节我们要进行相应的处理，具体见代码。

#include<bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define lson k<<1
#define rson k<<1|1
//#define getchar nc
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int INF = 0x3f3f3f3f;
const ll INF64 = 1e18;

inline char nc(){
    static char buf[100005],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    char ch=getchar(); int sum=0; int f=0;
    while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
    while(isdigit(ch)) sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar();
    return f?-sum:sum;
}
const int maxn=1e3+5;
int n,d;
char a[maxn][maxn];
int nearest[maxn][maxn];
int v[maxn][maxn];
int ans[maxn][maxn];
int mark[maxn][maxn];
int vis[maxn][maxn];
const int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
struct Node{
    int x,y,t;
};
queue<Node>q; 
inline bool in(int x,int y){
    return x>=1&&x<=n&&y>=1&&y<=n;
}
inline bool check(int x,int y,int t){
    return t/d<=nearest[x][y]-1;
}
inline void bfs1(){
    queue<pii>q; while(!q.empty()) q.pop();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(a[i][j]=='#') q.push(mp(i,j)),vis[i][j]=1;
    while(!q.empty()){
        int x=q.front().F,y=q.front().S; q.pop();
        for(int i=0;i<4;i++){
            int xx=x+dx[i],yy=y+dy[i];
            if(!in(xx,yy)||a[xx][yy]=='#'||vis[xx][yy]) continue;
            nearest[xx][yy]=nearest[x][y]+1;
            vis[xx][yy]=1; q.push(mp(xx,yy));
        }
    }
}
inline void bfs2(){
    queue<Node>q; while(!q.empty()) q.pop();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(a[i][j]=='S')
                q.push((Node){i,j,0}),v[i][j]=0;
        }   
    while(!q.empty()){
        int x=q.front().x,y=q.front().y,t=q.front().t; q.pop();
        if(t/d>=nearest[x][y]){
            mark[x][y]=1; continue;
        } 
        for(int i=0;i<4;i++){
            int xx=x+dx[i],yy=y+dy[i],tt=t+1;
            if(!in(xx,yy)||v[xx][yy]!=-1||a[xx][yy]=='#') continue;
            if(check(xx,yy,t)) v[xx][yy]=tt,q.push((Node){xx,yy,tt}); 
        }
    }
}
struct Point{
    int x,y,k;
    bool operator <(const Point &tmp)const{
        return tmp.k>k;
    }
};
inline void bfs3(){
    priority_queue<Point>q; while(!q.empty()) q.pop();
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(v[i][j]!=-1) q.push((Point){i,j,v[i][j]}),vis[i][j]=1;
    while(!q.empty()){
        int x=q.top().x,y=q.top().y,k=q.top().k; q.pop();
        if(!k) continue;
        for(int i=0;i<4;i++){
            int xx=x+dx[i],yy=y+dy[i];
            if(!in(xx,yy)||vis[xx][yy]||a[xx][yy]=='#') continue;
            vis[xx][yy]=1; q.push((Point){xx,yy,k-1});
        }
    }
}
int main(){
    n=read(); d=read();
    for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
    bfs1();
    memset(v,-1,sizeof(v)); 
    bfs2();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(v[i][j]!=-1){
                v[i][j]/=d;
                if(mark[i][j]) v[i][j]--;
            }
    bfs3();
    int res=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            res+=vis[i][j];
    printf("%d\n",res);
    return 0;
}