BoardCover

Timeout Answer

#include <stdio.h>
#include <assert.h>

int testNum, row, col;
int Board[20][20];
int whiteCnt;
int ans;

FILE *fin, *fout;

void sub(int sR, int sC, int prevShape);

void printBoard(FILE *fp)
{
    for (int r=0; r<row; r++)
    {
        for(int c=0; c<col; c++)
            fprintf(fp, "%d ", Board[r][c]);
        fprintf(fp, "\n");
    }
}

int main()
{
    //fin = fopen("in.txt", "r");
    //fout = fopen("out.txt", "w");

    //fscanf(fin, "%d",&testNum);
    scanf("%d",&testNum);
    for (int ii=0; ii<testNum; ii++)
    {
        for (int r=0; r<row; r++)
            for (int c=0; c<col; c++)
                Board[r][c] = -1;
        whiteCnt = 0;
        ans = 0;

        //fscanf(fin, "%d%d",&row,&col);
        scanf("%d%d",&row,&col);
        char newline;
        //fscanf(fin, "%c", &newline);
        scanf("%c", &newline);

        for (int r=0; r<row; r++)
        {
            char buffer[20] = {0, };
            fgets(buffer, 20, stdin);

            for (int c=0; c<col; c++)
            {
                if(buffer[c]=='#')  Board[r][c] = 0;
                else if(buffer[c]=='.') { Board[r][c] = 1; whiteCnt++; }
                else assert(0);
            }
        }

        // do my work
        //printBoard(fout);
        sub(0, 0, 0);
        //fprintf(fout, "\nans = %d\n", ans);
        printf("ans=%d\n", ans);
    }

    //fclose(fin);
    //fclose(fout);
    return 0;
}

void sub(int sR, int sC, int prevShape)
{
    //fprintf(fout, "--------------------\n");
    //fprintf(fout, "row=%d, col=%d, whiteCnt=%d, sR=%d, sC=%d\n", row, col, whiteCnt, sR, sC);
    //printf("row=%d, col=%d, whiteCnt=%d, sR=%d, sC=%d\n", row, col, whiteCnt, sR, sC);
    //printBoard(fout);

    if (whiteCnt == 0)
    {
        ans++;
        //fprintf(fout, "ok! return. ans=%d\n", ans);
        //printf("ok! return.\n");
        return;
    }

    if (whiteCnt < 3)
    {
        //fprintf(fout, "no room. stop here. whiteCnt=%d\n", whiteCnt);
        //printf("no room. stop here. whiteCnt=%d\n", whiteCnt);
        return;
    }

    if (whiteCnt % 3 != 0)
    {
        //fprintf(fout, "not multiple of 3. stop here. whiteCnt=%d\n", whiteCnt);
        //printf("not multiple of 3. stop here. stop here. whiteCnt=%d\n", whiteCnt);
        return;
    }

    for (int r=sR; r<row-1; r=r+1)
    {
        int c = (r==sR)? sC: 0;
        while (c < col-1)
        {
            //fprintf(fout, "(%d %d) ", r, c);
            // shape1
            // 1 1
            // x 1
            if (r+1<row && c+1<col && Board[r][c]==1 && Board[r][c+1]==1 && Board[r+1][c+1]==1) {
                //fprintf(fout, "%d row, %d col, shape 1 matched\n", r, c);
                Board[r][c]=2; Board[r][c+1]=2; Board[r+1][c+1]=2;
                whiteCnt-=3;
                if (c <= col-4)
                    sub(r, c+2, 1);
                else
                    sub(r+1, 0, 1);
                //fprintf(fout, "%d row, %d col : shape 1 roleback\n", r,c );
                whiteCnt+=3;
                Board[r][c]=1; Board[r][c+1]=1; Board[r+1][c+1]=1;
                //printBoard(fout);
            }

            // shape2
            // x 1
            // 1 1
            if (prevShape != 3 && r+1<row && c+1<col && Board[r][c+1]==1 && Board[r+1][c]==1 && Board[r+1][c-1]==1) {
                //fprintf(fout, "%d row, %d col, shape 2 matched\n", r, c);
                Board[r][c]=2; Board[r+1][c]=2; Board[r+1][c-1]=2;
                whiteCnt-=3;
                if (c <= col-4)
                    sub(r, c+2, 2);
                else
                    sub(r+1, c, 2);
                //fprintf(fout, "%d row, %d col : shape 2 roleback\n", r, c);
                whiteCnt+=3;
                Board[r][c]=1; Board[r+1][c]=1; Board[r+1][c-1]=1;
            }
            // shape3
            // 1 x
            // 1 1
            if (prevShape != 3 && r+1<row && c+1<col && Board[r][c]==1 && Board[r+1][c]==1 && Board[r+1][c+1]==1) {
                //fprintf(fout, "%d row, %d col, shape 3 matched\n", r, c);
                Board[r][c]=2; Board[r+1][c]=2; Board[r+1][c+1]=2;
                whiteCnt-=3;
                sub(r, c+1, 3);
                //fprintf(fout, "%d row, %d col : shape 3 roleback\n", r, c);
                whiteCnt+=3;
                Board[r][c]=1; Board[r+1][c]=1; Board[r+1][c+1]=1;
                //printBoard(fout);
            }
            // shape4
            // 1 1
            // 1 x
            if (prevShape != 3 && r+1<row && c+1<col && Board[r][c]==1 && Board[r][c+1]==1 && Board[r+1][c]==1) {
                //fprintf(fout, "%d row, %d col, shape 4 matched\n", r, c);
                Board[r][c]=2; Board[r][c+1]=2; Board[r+1][c]=2;
                whiteCnt-=3;
                if (c <= col-4)
                    sub(r, c+2, 4);
                else
                    sub(r+1, c, 4);
                //fprintf(fout, "%d row, %d col : shape 4 roleback\n", r, c);
                whiteCnt+=3;
                Board[r][c]=1; Board[r][c+1]=1; Board[r+1][c]=1;
                //printBoard(fout);
            }
            c = c + 1;
        }
    }

    //fprintf(fout, "no. return\n");
}