[HOJ 283][Codeforces #180]Grid coloring

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

這題看起來好複雜QAQ
那不如從K=2的情況下手吧
為了方便說明，這裡只討論N<=M的情況，N>M時只要對稱即可
首先，我們可以保證得到一半以上的分數
方法是，將矩形分成N列分別嚴格依照規則塗色(只考慮橫向的等不等於，以下稱列規則)，這樣可以保證得到(M-1)*N分
所以我們已經有一半的分數了
那接下來就是從剩下的一半至少再拿一半(四分之一)
可以發現，列與列之間有可能以經不小心喇到一些分數，而不相鄰的兩列之間已經沒有關聯，因此我們來討論兩列之間的分數可以怎麼喇(?)
首先，可以發現，如果將第n列的顏色，0轉1，1轉0，這一列還是遵守著列規則的
但是，和第n-1列的情況呢？
原本有得分的變沒得分，沒得分的變有得分，分數從x變成M-x了！
因此，只要挑分數比較高的情況斟酌去做顏色的反轉，就可以保證每兩列之間獲得不小於一半的分數！
所以總分就超過3/4了
這題就這樣被完美的解決~

等等等，別像我一樣忘了還有K=1的情況啦XD

code:

#include<cstdio>
#include<algorithm>
#include<cassert>
using namespace std;
int N,M,K;
char GRID[2001][2001];
int ANS[1000][1000];
bool Check()
{
    int cnt=0,sum=0;
    for(int r=0;r<2*N-1;r++)
    {
        for(int c=(r%2==0?1:0);c<2*M-1;c+=2)
        {
            const char v=GRID[r][c];
            sum++;
            if(r%2==0&&(ANS[r/2][c/2]==ANS[r/2][c/2+1])==(v=='E'))cnt++;
            if(r%2==1&&(ANS[r/2][c/2]==ANS[r/2+1][c/2])==(v=='E'))cnt++;
        }
    }
    return cnt>=sum*3/4;
}
bool Solve()
{
    assert(K>=1);
    if(K==1)
    {
        for(int i=0;i<N;i++)for(int j=0;j<M;j++)ANS[i][j]=0;
        return Check();
    }
    bool flipped=false;
    if(N>M)
    {
        flipped=true;
        for(int i=0;i<2*N-1;i++)for(int j=i+1;j<2*max(N,M)-1;j++)swap(GRID[i][j],GRID[j][i]);
        swap(N,M);
    }
    for(int r=0;r<N;r++)
    {
        int pre=ANS[r][0]=0;
        for(int c=1;c<M;c++)ANS[r][c]=(GRID[r*2][c*2-1]=='E'?pre:(pre^=1));
    }
    for(int r=1;r<N;r++)
    {
        int cnt=0;
        for(int c=0;c<M;c++)if((ANS[r-1][c]==ANS[r][c])==(GRID[r*2-1][c*2]=='E'))cnt++;
        if(cnt*2<M)for(int c=0;c<M;c++)ANS[r][c]^=1;
    }
    assert(Check());
    if(flipped)
    {
        for(int i=0;i<N;i++)for(int j=i+1;j<max(N,M);j++)swap(ANS[i][j],ANS[j][i]);
        swap(N,M);
    }
    return true;
}
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d%d%d",&N,&M,&K);
    for(int i=0;i<2*N-1;i++)
    {
        for(int j=(i%2==0?1:0);j<2*M-1;j+=2)
        {
            char &c=GRID[i][j]=getchar();
            while(c!='N'&&c!='E')c=getchar();
        }
    }
    if(Solve())
    {
        puts("YES");
        for(int r=0;r<N;r++)
        {
            for(int c=0;c<M;c++)
            {
                if(c)putchar(' ');
                printf("%d",ANS[r][c]+1);
            }
            puts("");
        }
    }
    else puts("NO");
    return 0;
}