[HOJ 283] Grid coloring

作法：

當$k=1$時作法是顯然的。接下來我們構造只要兩種顏色就可以滿足$\frac{3}{4}$以上的方法。首先把第一列按照不違反左右限制的方法塗完。並且最左邊行和最右邊行的格子的塗法為滿足他和他上面那個格子的限制為準。剩下的格子由上往下一列一列填，同列時由左往右填。假設當前格子為$A$，左邊格子為$B$，上面格子為$C$，右上方格子為$D$，那麼$B$會透過$A$左邊界的條件來限制$A$要放什麼，$C$則是透過上邊界，$D$則是得往下走再往左走來限制。如果這三個限制條件是一樣的話就直接放上那個顏色即可，否則一定有兩個限制條件的顏色一樣，選那個顏色塗即可。而證明也不難，只要發現到連續使用兩次上述塗法至多會跑出一個不合法的地方就可以了。

這題原本是codeforces的題目，官方解和我的不太一樣，也可以參考看看。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+10 ;
int ri[maxn][maxn],dn[maxn][maxn] ; /// 1 : not equal
int ans[maxn][maxn] ;
char s[maxn] ;
main()
{
    int n,m,k,num=0 ; scanf("%d%d%d",&n,&m,&k) ;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1) ;
        for(int j=1;j<m;j++) if(s[j]=='N')
            num++ , ri[i][j]=1 ;
        if(i==n) break ;
        scanf("%s",s+1) ;
        for(int j=1;j<=n;j++) if(s[j]=='N')
            num++ , dn[i][j]=1 ;
    }
    if(k==1)
    {
        if(2*n*m-m-n<=4*num){printf("NO\n") ; return 0 ;}
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
            printf("1%c",j==m?'\n':' ') ;
        return 0 ;
    }
    printf("YES\n") ;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
    {
        if(i==1)
        {
            ans[i][j]=ans[i][j-1]^ri[i][j-1] ;
            continue ;
        }
        if(j==1 || j==m)
        {
            ans[i][j]=ans[i-1][j]^dn[i-1][j] ;
            continue ;
        }
        int x=ans[i][j-1]^ri[i][j-1],y=ans[i-1][j]^dn[i-1][j] ;
        int z=ans[i-1][j+1]^dn[i-1][j+1]^ri[i][j] ;
        if(x==y || x==z) ans[i][j]=x ;
        else ans[i][j]=y ;
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
        printf("%d%c",ans[i][j]+1,j==m?'\n':' ') ;
}