Page 1 of 1
387, can you give me some test case?
Posted: Tue Oct 08, 2002 7:41 am
by pendryko
my brain is dump now,
help me please?
thanks..
Posted: Tue Oct 08, 2002 8:03 am
by Dominik Michniewski
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
Posted: Wed Oct 09, 2002 4:07 am
by pendryko
#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. 
387 - A Puzzling Problem
Posted: Wed May 26, 2004 8:11 pm
by pipo
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...
please tell some examples to me about input and output...
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]
Re: WA 387
Posted: Sat Nov 07, 2009 3:44 pm
by bleed1979
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.
Re: WA 387
Posted: Wed May 21, 2014 2:55 pm
by hpjhc
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;
}
Re: WA 387
Posted: Wed May 21, 2014 8:20 pm
by brianfry713
Try input:
Code: Select all
2
4 4
1010
0101
1010
0101
4 4
0101
1010
0101
1010
0
My AC code prints: