519 - Puzzle (II)

[sarker306]

I did not think the problem would be easy. I tried to predetermine if the puzzle could be solved, but this could not save me from getting TLE.
I tried to solve the puzzle by tiling (0,0), then (0,1)... row major basis.
If number of jut != number of cavity, no result.
If number of frontside != 2*(row + column), no result. ( m means number of row, n means number of column ).
I could not find any other prechecking options.
If any idea can help me detect where I am running slow, or can help me find any place to prune earlier, I will be grateful.

Code: Select all

#include<stdio.h>

int m, n, lim;
char value[100];
char piece[40][5], puzzle[7][7], used[40], flag;
/* pieces .. [0]-> top , [1]-> right, [2]->bottom, [3]->left */

int placable(int rank, int r, int c){
    if(r==0 && piece[rank][0]!='F') return 0;
    if(r==m-1 && piece[rank][2]!='F') return 0;
    if(c==0 && piece[rank][3]!='F') return 0;
    if(c==n-1 && piece[rank][1]!='F') return 0;
    if(r!=0 && piece[rank][0]=='F') return 0;
    if(r!=m-1 && piece[rank][2]=='F') return 0;
    if(c!=0 && piece[rank][3]=='F') return 0;
    if(c!=n-1 && piece[rank][1]=='F') return 0;

    if(r>0 && value[piece[puzzle[r-1][c]][2]]+value[piece[rank][0]]!=0) return 0;
    if(c>0 && value[piece[puzzle[r][c-1]][1]]+value[piece[rank][3]]!=0) return 0;
    return 1;
}

void print_state(){
    int i, j;

    puts("\n****************\n");
    for(i=0;i<m;i++){
        for(j=0;j<n;j++) printf("%2d ", puzzle[i][j]);
        puts("");
    }

    puts("\n****************");
}

void backtrack(int r, int c){
    int i, j;

    if(r==m){
        flag=1;
      /*  print_state(); */
        return ;
    }

    for(i=0;i<lim && flag==0;i++){
        if(used[i]==0 && placable(i, r, c)){
            puzzle[r][c]=i;
            used[i]=1;
            if(c+1<n) backtrack(r, c+1);
            else backtrack(r+1, 0);
            used[i]=0;
        }
    }

    puzzle[r][c]=-1;
}

void init_puzzle(){
    int i, j;

    for(i=0;i<lim;i++) used[i]=0;
    for(i=0;i<m;i++) for(j=0;j<n;j++) puzzle[i][j]=-1;
    flag=0;
}

int precheck(){
    int i, j, rescorner=0, resside=0, resO=0, resI=0, x;

    for(i=0;i<lim;i++){
        for(j=x=0;piece[i][j];j++){
            if(piece[i][j]=='F') x++;
            else if(piece[i][j]=='O') resO++;
            else if(piece[i][j]=='I') resI++;
            else return 0;
        }

        if(x>=2) rescorner++;
        if(x) resside+=x;
    }

    /*if( rescorner==1 && m!=1 && n!=1) return 0;
    if( rescorner==2 && (m!=1 || n!=1)) return 0;
    if( rescorner!=4 ) return 0;*/
    if( resside!=2*(m+n)) return 0;
    if(resI!=resO) return 0;
    return 1;
}

void solve(){
    if(precheck()) backtrack(0,0);
}

int main(){
    int i;

    value['I']=1, value['F']=5, value['O']=-1;
    while(scanf("%d%d", &m, &n)!=EOF){
        if(m==0 && n==0) break;
        for(i=0, lim=m*n;i<lim;i++) scanf("%s", piece[i]);
        init_puzzle();
        solve();
        if(flag) puts("YES");
        else puts("NO");
    }

    return 0;
}

I will try to hand-make some test cases, in the meanwhile, any critical I/O will be helpful for me. Thank you.

[shiguowang]

The problem says "She has started with a small one containing 15 pieces", so threre are two cases: 1:n==3 m == 5; 2:n == 5, m== 3; but it is not.Am I wrong?

[metaphysis]

To make the description of problem clearer.
The test data:

Code: Select all

1 2
FOFF
FFFI
2 1
FFOF
IFFF
2 1
FFIF
OFFF
2 2
FFFF
FFFF
FFFF
FFFF
0 0

output:

Code: Select all

YES
YES
YES
NO

means the corner piece have two flat sides, and two sides with jut or cavity; pieces at row 1 have a top flat side and other three sides with jut or cavity...
At first, I thought one piece can have three flat sides and one side with jut or cavity.