HDOJ 4146 Flip Game

スーパーゲート:
http://acm.hdu.edu.cn/showproblem.php?pid=4146
1つの碁盤があって、白黒の2色の駒が碁盤にいっぱいで、黒はbで、白はwです.碁盤は左から右へ番号1~N、上から下へ番号1~N、そして一連の命令(Xi,Xj)を実行し、Xi行目とXj列目を反転させることで、(Xi,Xj)という点にある駒が2回反転されていることがわかるので、変わっていない.タイトルは一連の命令を実行した後、碁盤に残った白子の数を出力することを要求する.
テーマデータ量(1<=N<=1000,0<=Q<=100000)は、直接シミュレーション法を用いて、各命令がその行とその列を遍歴して反転するとTLEが容易になる.2つの配列で各行と各列が反転された回数を記録することができ、その点が存在する行と列の反転回数の和が偶数であれば、その点は元のままであり、そうでなければ逆になり、時間を節約できるが、かなり暴力的です.

#include<stdio.h>
#include<string.h>
int map[1050][1050];
int Qa[100010],Qb[100010];
int main () {
    //freopen("1.txt","r",stdin);
    int t,n,q,qa,qb,i,j,k,sum,len;
    char temp[1050];
    scanf("%d",&t);
    for (i=0;i<t;i++) {
        memset(map,0,sizeof(map));
        memset(Qa,0,sizeof(Qa));
        memset(Qb,0,sizeof(Qb));
        scanf("%d",&n);
        sum = 0;
        for (j=1;j<=n;j++) {
            scanf("%s",temp);
            len = strlen(temp);
            for (k=0;k<len;k++) {
                if (temp[k]=='b') map[j][k+1] = 0;
                else if (temp[k]=='w') map[j][k+1] = 1;
            }
        }
        scanf("%d",&q);
        for (j=0;j<q;j++) {
            scanf("%d%d",&qa,&qb);
            Qa[qa] ++;
            Qb[qb] ++;
        }
        for (j=1;j<=n;j++) {
            for (k=1;k<=n;k++) {
                if ((Qa[j]+Qb[k])%2==0 && map[j][k]) sum ++;
                if ((Qa[j]+Qb[k])%2==1 && !map[j][k]) sum ++;
            }
        }
        printf("Case #%d: %d
",i+1,sum);
    }
    return 0;
}