题解：P16162 [ICPC 2016 NAIPC] Whiteboard

leo120306 · 2026-05-10 16:33:44 · 题解

假设每一个位置被走到的时间戳集合为 S_{i,j}，颜色是 c_{i,j}。

显然的是：

• 假设 a=\max_{c_{i,j}=\texttt{\#}} \max S_{i,j}，b=\max\{t+1,\min_{c_{i,j}=\texttt{.}} \max S_{i,j}\}，其中 t 是总路径长度，则 a 是最早断墨位置，b-1 是最晚断墨位置。当 a>b-1，就是无解。

于是问题转化为求 \max S_{i,j}。容易发现可以拆成横纵来维护，对于每一行、列，维护一棵区间推平单点查询线段树，按顺序在线段树上操作，每次将作用区间推平为操作编号即可。每一个操作需要记录起始位置与起始时间戳，则某个位置在这一操作区间的时间戳即为起始时间戳与起始位置到询问位置的距离之和。最后横纵取 \max 即可。时间复杂度 O((hm+n)\log hm)。

int h,w,n;
string s[N];

struct opt{
    int sx,sy;ll t;
}q[N];

struct SGT{
    int laz[4*N],dat[4*N];
    void pushdown(int o){
        if(laz[o]){
            laz[o*2]=dat[o*2]=laz[o*2+1]=dat[o*2+1]=laz[o];
            laz[o]=0;
        }
    }
    void modify(int o,int l,int r,int L,int R,int x){
        if(L<=l&&r<=R){
            laz[o]=dat[o]=x;
            return;
        }
        pushdown(o);
        int mid=(l+r)>>1;
        if(L<=mid)modify(o*2,l,mid,L,R,x);
        if(R>mid)modify(o*2+1,mid+1,r,L,R,x);
    }
    int query(int o,int l,int r,int x){
        if(l==r)return dat[o];
        pushdown(o);
        int mid=(l+r)>>1;
        if(x<=mid)return query(o*2,l,mid,x);
        else return query(o*2+1,mid+1,r,x);
    }
}sgt1,sgt2;
#define id1(x,y) (((y)-1)*h+(x))
#define id2(x,y) (((x)-1)*w+(y))

void main(){
    cin>>h>>w>>n;
    for(int i=1;i<=h;i++)cin>>s[i],s[i]=' '+s[i];
    for(int i=1;i<=h/2;i++)swap(s[i],s[h-i+1]);
    int x=1,y=1;ll t=1;
    for(int i=1;i<=n;i++){
        string d;int dis;cin>>d>>dis;
        if(i!=1){
            if(d=="up")x++;
            if(d=="down")x--;
            if(d=="left")y--;
            if(d=="right")y++;
        }else dis++;
        q[i]={x,y,t};
        if(d=="up"){
            sgt1.modify(1,1,h*w,id1(x,y),id1(x+dis-1,y),i);
            x=x+dis-1;
        }
        if(d=="down"){
            sgt1.modify(1,1,h*w,id1(x-dis+1,y),id1(x,y),i);
            x=x-dis+1;
        }
        if(d=="left"){
            sgt2.modify(1,1,h*w,id2(x,y-dis+1),id2(x,y),i);
            y=y-dis+1;
        }
        if(d=="right"){
            sgt2.modify(1,1,h*w,id2(x,y),id2(x,y+dis-1),i);
            y=y+dis-1;
        }
        t+=dis;
    }
    ll ans1=0,ans2=t;
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++){
            int idx1=sgt1.query(1,1,h*w,id1(i,j));
            int idx2=sgt2.query(1,1,h*w,id2(i,j));
            int idx=max(idx1,idx2);
            if(!idx&&s[i][j]=='#'){
                puts("-1 -1");cout<<endl;
                return;
            }
            if(!idx)continue;
            ll val=q[idx].t+abs(q[idx].sx-i)+abs(q[idx].sy-j);
            if(s[i][j]=='#')ans1=max(ans1,val);
            else ans2=min(ans2,val);
        }
    if(ans1>=ans2)puts("-1 -1");
    else printf("%lld %lld\n",ans1,ans2-1);
}