[USACO 2014 Gold] Building a Ski Course

作法：

首先可以觀察到，如果邊長為 B 的正方形可以蓋出所求的圖形，那麼邊長為 B-1 的也可以蓋出來，因為邊長為 B 的正方形可以由 B-1 的蓋四次得到，所以可以二分答案。如果直接思考第一步應該要蓋在哪裡，會發現根本沒辦法決定，因為之後可能有一堆地方被新的正方形覆蓋掉了。考慮把整個過程反過來，會發現最後一次壓下去的那塊 B*B 的正方形中一定同為 S 或同為 R 。再考慮最後第二次壓下去的那塊 B*B 的正方形，他除了「最後一次壓下去的那塊正方形內部的格子」以外的格子都必須同為 S 或 R ，而和最後一次壓下去的那塊交集的部份不管是什麼都可以，反正等等就會被覆蓋掉了。所以我們就可以得到這樣的算法：從給定的圖開始，每次在圖中尋找整塊都是 S 或整塊都是 R 的 B*B 的正方形，然後把正方形的內部都標記成「此格可以當 R 也可以當 S 」，並且在之後判斷是否為整塊都是 R（S）的正方形時放寬這種格子的限制。如果做到最後全部的格子都被覆蓋了，那麼就是可以，否則就不行。在實作上，我是對每個點算出以他為正方形右下角的最大正方形邊長，如果邊長>=B，並且之前還沒有在這個位置蓋下 B*B 的正方形，那麼就把他紀錄起來，當跑完 n*m 格之後將所有剛才找到的正方形把他蓋下去，重複這個動作直到不能在做為止。這樣可以把原本O(n^2 m^2 log(n+m)) 的算法時間壓到不至於TLE。

code :

#include<bits/stdc++.h>
#define MIN(x,y,z) min(min(x,y),z)
using namespace std;
const int maxn=100+10 ;
 
int dp[2][maxn][maxn] ;
int tmp[2*maxn*maxn] ;
int n,m,G[maxn][maxn],G2[maxn][maxn] ;
bool used[maxn][maxn] ;
 
void cover(int x,int y,int d)
{
    used[x][y]=1 ;
    int xd=3 ;
    for(int i=x-d+1;i<=x;i++) for(int j=y-d+1;j<=y;j++)
        xd&=G[i][j] , G[i][j]=3 ;
    assert(xd>0) ;
}
 
bool check(int d)
{
    memset(used,0,sizeof(used)) ;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
        G[i][j]=G2[i][j] ;
    while(1)
    {
        int cnt=0 ;
        for(int z=0;z<2;z++)
            for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
        {
            dp[z][i][j]=0 ;
            if(!(G[i][j]&(1<<z))) continue ;
            dp[z][i][j]=MIN(dp[z][i][j-1],dp[z][i-1][j],
                            dp[z][i-1][j-1])+1 ;
            if(dp[z][i][j]>=d && !used[i][j])
                tmp[cnt++]=i , tmp[cnt++]=j ;
        }
        if(!cnt) break ;
        for(int i=0;i<cnt;i+=2) cover(tmp[i],tmp[i+1],d) ;
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
        if(G[i][j]!=3) return 0 ;
    return 1 ;
}
 
main()
{
    freopen("skicourse.in","r",stdin) ;
    freopen("skicourse.out","w",stdout) ;
    scanf("%d%d",&n,&m) ;
    for(int i=1;i<=n;i++)
    {
        char s[maxn] ; scanf("%s",s+1) ;
        for(int j=1;j<=m;j++)
            G[i][j]=G2[i][j]=(s[j]=='R' ? 1 : 2) ;
    }
 
    int l=1 , r=min(m,n)+1 ;
    while(r-l>1)
    {
        int mid=(r+l)/2 ;
        if(check(mid)) l=mid ;
        else r=mid ;
    }
    printf("%d\n",l) ;
}