uva 141 The Spot Game

思考這題的時候，不用怕因為要一直往前 check 而導致 TLE，測資的大小可以以這種方式在時間內跑完。
所以直接把過程 code 即可。

我有做一個黑點 counter 的比較，如果 counter 不同，就一定不同，不用再掃四個二維陣列。

function 的部分只要掃轉移個方向的，其他三個情形直接呼叫同一個 function 來轉。

#include <stdio.h>
#include <stdlib.h>

struct grid{
    int g1[51][51];
    int g2[51][51];
    int g3[51][51];
    int g4[51][51];
    int counter;
};
struct grid boxs[100];

void r90(int a[51][51], int b[51][51], int N){
    int i,j,m,n;

    for(i=N,n=1;i>=1;--i,++n){
        for(j=1,m=1;j<=N;++j,++m){
            b[m][n]=a[i][j];
        }
    }

    return;
}

int check(struct grid a,int b[51][51],int N,int bcounter){
    int i,j,ok;

    if(a.counter!=bcounter)
        return 1;

    ok=0;
    for(i=1;i<=N;++i){
        for(j=1;j<=N;++j){
            if(a.g1[i][j]!=b[i][j]){
                ok=1;
            }
        }
    }
    if(ok==0)
        return 0;

    ok=0;
    for(i=1;i<=N;++i){
        for(j=1;j<=N;++j){
            if(a.g2[i][j]!=b[i][j]){
                ok=1;
            }
        }
    }
    if(ok==0)
        return 0;

    ok=0;
    for(i=1;i<=N;++i){
        for(j=1;j<=N;++j){
            if(a.g3[i][j]!=b[i][j]){
                ok=1;
            }
        }
    }
    if(ok==0)
        return 0;

    ok=0;
    for(i=1;i<=N;++i){
        for(j=1;j<=N;++j){
            if(a.g4[i][j]!=b[i][j]){
                ok=1;
            }
        }
    }
    if(ok==0)
        return 0;

    return 1;
}

int main(void){
    int N, top, i,j;
    int x,y;
    char c;
    int pass;

    while(1){
        scanf("%d",&N);
        if(N==0) break;

        for(i=1,top=-1,pass=0;i<=2*N;++i){
            scanf("%d %d %c",&x,&y,&c);
            if(pass==1) continue;
            if(top==-1){
                boxs[++top].counter=1;
                boxs[top].g1[x][y]=1;
                r90(boxs[top].g1,boxs[top].g2, N);
                r90(boxs[top].g2,boxs[top].g3, N);
                r90(boxs[top].g3,boxs[top].g4, N);
            }else{
                ++top;
                boxs[top]=boxs[top-1];
                if(c=='+'){
                    boxs[top].g1[x][y]=1;
                    ++boxs[top].counter;
                }else{
                    boxs[top].g1[x][y]=0;
                    --boxs[top].counter;
                }

                for(j=0;j<top;++j){
                    if( check(boxs[j],boxs[top].g1,N,boxs[top].counter) ==0 ){
                        if(i%2==0){
                            printf("Player 1 wins on move %d\n",i);
                        }else{
                            printf("Player 2 wins on move %d\n",i);
                        }
                        pass=1;
                        break;
                    }
                }

                r90(boxs[top].g1,boxs[top].g2, N);
                r90(boxs[top].g2,boxs[top].g3, N);
                r90(boxs[top].g3,boxs[top].g4, N);
            }
        }

        if(i>2*N && pass!=1)
            printf("Draw\n");
    }


    return 0;
}