## 519 - Puzzle (II)

Moderator: Board moderators

sarker306
New poster
Posts: 2
Joined: Sat Sep 05, 2009 3:50 am

### 519 - Puzzle (II)

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
New poster
Posts: 2
Joined: Sun Mar 08, 2015 10:54 am

### Re: 519 - Puzzle (II)

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
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 519 - Puzzle (II)

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.