## 387 - A Puzzling Problem

Moderator: Board moderators

pendryko
New poster
Posts: 3
Joined: Tue Oct 08, 2002 7:10 am

### 387, can you give me some test case?

my brain is dump now,

thanks..

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
What kind of algorithm do you use ?
I think, that this problem haven't any special cases - all depends from chosen algorithm ... I got accepted this problem first time when I try

Domnik

pendryko
New poster
Posts: 3
Joined: Tue Oct 08, 2002 7:10 am
#include <stdio.h>
#include <stdlib.h>

int per;
int terpakai[100],se[100],b[100],k[100];
char x[100][100][100];
char hasil[100][100];

int masukan(){
int i,j,jtemp;
int p,q,p1,q1;
int curr,cek;
curr=1;
cek=1;
memset(&hasil,'0',sizeof(hasil));
for(i=0;i<4&&curr<=per&&cek;i++){
for(j=0;j<4&&curr<=per&&cek;j++){
if(hasil[j]=='0'){
jtemp=j;
if(x[se[curr]-1][0][0]!='1'){
for(p=0;p<k[se[curr]-1];p++){
if(x[se[curr]-1][0][p]=='0'){
jtemp--;
}
}
}
p1=i;
if(((p1+b[se[curr]-1]-1>=0)&&
(p1+b[se[curr]-1]-1<4))&&
((jtemp+k[se[curr]-1]-1>=0)&&
(jtemp+k[se[curr]-1]-1<4))){
cek=1;
for(p=0;p<b[se[curr]-1]&&cek;p++){
q1=jtemp;
for(q=0;q<k[se[curr]-1]&&cek;q++){
if(x[se[curr]-1][p][q]=='1'){
if (hasil[p1][q1]=='0'){
hasil[p1][q1]=se[curr]+48;
}else
cek=0;
}
q1++;
}
p1++;
}
}else{
cek=0;
}
curr++;
}
}
}
return cek;
}

int tulis(){
int i,j;
int cek;
cek = masukan();
for(i=0;i<4&&cek;i++){
for(j=0;j<4&&cek;j++){
if(hasil[j]=='0')
cek=0;
}
}
if (cek==1){
for(i=0;i<4;i++){
for(j=0;j<4;j++){
printf("%c",hasil[j]);
}
printf("\n");
}
per=0;
return 0;
}else
return 1;
}

void permutasi(int ya, int terpakai[100], int ke){
int i,n;
se[ke]=ya;
n=1;
if (ke==per){
n=tulis();
}
if(n==1){
for(i=1;i<=per;i++){
if(terpakai==0){
terpakai=1;
permutasi(i,terpakai,ke+1);
terpakai=0;
}
}
}
}

void mulai(){
int i,j;

memset(&terpakai,0,sizeof(terpakai));
for(j=1;j<=per;j++){
if(x[j-1][0][0]=='1'){
terpakai[j]=1;
permutasi(j,terpakai,1);
terpakai[j]=0;
}
}
if ((j>per)&&(per!=0)){
printf("No solution possible\n");
}
}

int main(){
int p,q,r,ktk,cek;
cek=0;
while((scanf("%d",&per)==1)&&(per!=0)){
if (cek==1)
printf("\n");
cek=1;
for(p=0;p<per;p++){
scanf("%d %d",&b[p],&k[p]);
getchar();
for(q=0;q<b[p];q++){
fgets(x[p][q],sizeof(x[p][q]),stdin);
}
}
ktk=0;
for(p=0;p<per;p++){
for(q=0;q<b[p];q++){
for(r=0;r<k[p];r++){
if(x[p][q][r]=='1')
ktk++;
}
}
}
if (ktk>=16){
mulai();
}else
printf("No solution possible\n");
}
return 0;
}

i use permutasi.
can we input the puzzle more than 5?
thanks.

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

### 387 - A Puzzling Problem

hi..

well.... I got WA... first.. my code is right on example input and output..

also, I have tested some inputs.. as a result, the output is right..

but, when I submit my code, I got WA...

I dont know why I got WA...

If the reason is,

If a count of pieces is more than 10, I know why I got WA.

but, Is a count of pieces is more than 10 ?

If it is, how the output is shown ?

If this reason was that I got WA, I only suspend this reason...

If this reason isn't, I really dont know why I got WA..

please show some examples of input and output to me. [/cpp]

bleed1979
New poster
Posts: 8
Joined: Thu Oct 08, 2009 5:34 am

### Re: WA 387

1.I think use DFS is so easy to solve this problem.
2.Normal cases are not hard for coding. I give 2 critical test cases.
Input

Code: Select all

``````2
4 4
1111
1111
1111
1111
1 1
1
1
1 1
1
0
``````
Output

Code: Select all

``````No solution possible

No solution possible
``````
Every piece has to be used.
Judge World - problem solving is a routine.
http://bleed1979.myweb.hinet.net

hpjhc
New poster
Posts: 17
Joined: Wed Jun 26, 2013 10:35 am

### Re: WA 387

Why WA?

Code: Select all

``````#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<set>
#include<vector>
#include<queue>
#include<assert.h>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;

int n;
int row[5], col[5], vis[5], grid[5][5];
char s[5][5][5];
bool dfs(int r, int c)
{
int temp[5][5];
if (r == 4){
for (int i = 0; i < n; i++){
if (!vis[i])
return false;
}
return true;
}
if (c == 4)
return dfs(r + 1, 0);
memcpy(temp, grid, sizeof(grid));
for (int i = 0; i < n; i++)
{
if (vis[i])
continue;
if (grid[r][c] == 0 && s[i][0][0] == '1')
{
if (r + row[i] - 1 >= 4 || c + col[i] - 1 >= 4)
continue;
for (int j = 0; j < row[i]; j++)
{
for (int k = 0; k < col[i]; k++){
if (s[i][j][k] == '1' && grid[r + j][c + k])
goto next;
}
}
for (int j = 0; j < row[i]; j++)
{
for (int k = 0; k < col[i]; k++){
if (s[i][j][k] == '1')
grid[r + j][c + k] = i + 1;
}
}
vis[i] = 1;
if (dfs(r, c))
return true;
vis[i] = 0;
memcpy(grid, temp, sizeof(grid));
}
else if (grid[r][c] && s[i][0][0] == '0')
{
if (r + row[i] - 1 >= 4 || c + col[i] - 1 >= 4)
continue;
for (int j = 0; j < row[i]; j++)
{
for (int k = 0; k < col[i]; k++){
if (s[i][j][k] == '1' && grid[r + j][c + k])
goto next;
}
}
for (int j = 0; j < row[i]; j++)
{
for (int k = 0; k < col[i]; k++){
if (s[i][j][k] == '1')
grid[r + j][c + k] = i + 1;
}
}
vis[i] = 1;
if (dfs(r, c))
return true;
vis[i] = 0;
memcpy(grid, temp, sizeof(grid));
}
next:;
}
if (grid[r][c])
return dfs(r, c + 1);
return false;
}
int main(void)
{
int p = 1;
while (scanf("%d", &n), n)
{
if (p > 1)
puts("");
for (int i = 0; i < n; i++){
scanf("%d%d", &row[i], &col[i]);
for (int j = 0; j < row[i]; j++)
scanf("%s", s[i][j]);
}
memset(vis, 0, sizeof(vis));
memset(grid, 0, sizeof(grid));
if (dfs(0, 0)){
for (int i = 0; i < 4; i++){
for (int j = 0; j < 4; j++)
printf("%d", grid[i][j]);
puts("");
}
}
else
puts("No solution possible");
p++;
}
return 0;
}``````
Last edited by hpjhc on Thu May 22, 2014 3:46 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: WA 387

Try input:

Code: Select all

``````2
4 4
1010
0101
1010
0101
4 4
0101
1010
0101
1010
0
``````
My AC code prints:

Code: Select all

``````1212
2121
1212
2121
``````
Check input and AC output for thousands of problems on uDebug!