CF1799E 题解

· · 题解

提供一种 \Theta(\sum nm) 的做法。

对于一个联通块，称其合法当且仅当它满足题目所属条件（即任何两个格点之间最短路都等于曼哈顿距离）。

这一段只讨论只有一个联通块的情况。

观察一个合法联通块的边界，从最高点顺时针走，一定是：

  1. 先只向右向下走；
  2. 再只向左向下走；
  3. 再只向左向上走；
  4. 再只向右向上走。

如果设 L_i 表示第 i 行左侧 . 的数量，则联通块合法当且仅当：

  1. 对于所有 i 都有 L_i \leq L_{i-1} 或者 L_i \leq L_{i+1}；
  2. 对于右侧也满足上述条件；
  3. 每行 # 连续。

考虑一个将不合法的联通块扩充成最小合法联通块的算法：

先算出每行左侧有多少 .；

将 L_i 对 L_{i-1} 取 \min 得到 L_i'；

将 L_i 对 L_{i+1} 取 \min 得到 L_i''；

令 L_i 为 \max(L_i',L_i'')，并标记第 i 行最左侧的 L_i 个格子（标记表示这个格子不用放 #）。

不难发现这会得到每个 L_i 的可能最大值。

接着对右侧做同样的事情。

最后将所有未标记格子全部变成 #。（这同时处理了中间的空洞）

然后上面那个算法完全可以处理不连通的情况，但是有时候处理出来的 "最小合法联通块" 可能会不联通。

可以发现这种时候是若干个合法的联通块斜着分布，像这样：

易证直接用最短路把他们联通起来就是合法的。

贴上两段核心代码：

    // 处理 L[i] 和 R[i]
    L[0]=1; R[0]=m; 
    L[n+1]=1; R[n+1]=m;
    for(int i=1; i<=n; ++i) {
        R[i]=0;   
        while(R[i]<R[i-1]&&s[i][R[i]+1]=='.') vis[i][++R[i]]=1;
        L[i]=m+1; 
        while(L[i]>L[i-1]&&s[i][L[i]-1]=='.') vis[i][--L[i]]=1;
    }
    for(int i=n; i>=1; --i) {
        R[i]=0;   
        while(R[i]<R[i+1]&&s[i][R[i]+1]=='.') vis[i][++R[i]]=1;
        L[i]=m+1; 
        while(L[i]>L[i+1]&&s[i][L[i]-1]=='.') vis[i][--L[i]]=1;
    }
    for(int i=1; i<=n; ++i) 
        for(int u=1; u<=m; ++u)
            if(!vis[i][u]) s[i][u]='#';
    // 连接两个点
    int dx=P2.first >=P1.first  ? 1 : -1;
    int dy=P2.second>=P1.second ? 1 : -1;
    while(P1!=P2) {
              if(s[P1.first+dx][P1.second   ]=='#'&&P1.first !=P2.first ) P1.first +=dx;
         else if(s[P1.first   ][P1.second+dy]=='#'&&P1.second!=P2.second) P1.second+=dy;
         else if(P1.first!=P2.first) P1.first +=dx,s[P1.first][P1.second]='#';
         else                        P1.second+=dy,s[P1.first][P1.second]='#';
    }