BoardCover

Correct answer


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

int testNum, row, col;
int Board[20][20];
int whiteCnt;
int ans;
void sub();


FILE *fin, *fout;
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();
        //fprintf(fout, "\nans = %d\n", ans);
        printf("%d\n", ans);
    }
    //fclose(fin);
    //fclose(fout);
    return 0;
}

void sub()
{
    //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;
    }
    bool find=false;
    int r=0, c=0;
    for (r=0; r<row; r++)
    {
        for (c=0; c<col; c++)
        {
            if (Board[r][c]==1)
            {
                find=true;
                break;
            }
        }
        if(find==true)  break;
    }

    if (find == false)
    {
        //printf("no white.\n");
        ans++;
        return;
    }

    //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;
        sub();
        //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 (r+1<row && c-1>=0 && Board[r][c]==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;
        sub();
        //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 (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();
        //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 (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;
        sub();
        //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);
    }
    //fprintf(fout, "no. return\n");
}