## 11140 - Little Ali's Little Brother!

Moderator: Board moderators

Yes

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am

please someone help me. I don't know what's wrong with my code.
I'm getting crazy... I also considered diagonals... I wasn't doing that before.

[code]
#include<stdio.h>
#include<string.h>
#define MAX 50 + 1 + 1

int numCasos, N, M, S, n, m, cont, total;

void rec(int iG, int jG, int iB, int jB)
{
//printf("iG=%d jG=%d iB=%d jB=%d\n", iG, jG, iB, jB);
if(cont>=total) return;
if(iG>N || iG<1 || jG>M || jG<1 || visitado[iG][jG]==1) return;
if(iB>n || iB<1 || jB>m || jB<1) return;
if(bloco[iB][jB]=='.') return;
if(grid[iG][jG]=='.') return;

//printf("(%d, %d) deu certo!\n", iG, jG);
cont++;

rec(iG-1, jG, iB-1, jB);//acima
rec(iG+1, jG, iB+1, jB);//baixo
rec(iG, jG+1, iB, jB+1);//direita
rec(iG, jG-1, iB, jB-1);//esquerda

//diagonais
rec(iG-1, jG-1, iB-1, jB-1);//acima esquerda
rec(iG-1, jG+1, iB-1, jB+1);//acima direita
rec(iG+1, jG+1, iB+1, jB+1);//baixo direita
rec(iG+1, jG-1, iB+1, jB-1);//baixo esquerda
}

bool encontraPadrao(int iG, int jG, int iB, int jB)
{
if(total==0) return true; //pe
Regards,
[]'s
Andre

ferrizzi
New poster

Posts: 23
Joined: Thu Mar 30, 2006 5:42 pm
Location: Brazil

ferrizzi wrote:What about of the following input:

1
3 6 1
......
......
......
3 3
...
...
...

What would be the output? Yes or No?

I wrote my previous remark about the stupidity of 'disconnected pieces' based on common sense, without having solved the problem (I meant 'stupid' in a funny way, not in an insulting way, but I think you got that). Based on the problem description:
The pieces of this puzzle has horizontal or vertical edges
I intended to make a similar remark about empty pieces. Because empty pieces have no edges, I was going to say that it was stupid to consider their existence. But... I solved the problem, and there are empty pieces in the input(which is stupid in an insulting way).

So now I'm not so sure anymore about the non-existence of 'disconnected pieces' in this problem: if the problemsetter makes a mistake in one place, why wouldn't he do so in an other as well? (I don't mean that insulting; I made too many errors as a problemsetter myself). My best advice would be: don't make your solution dependent on the connectedness of pieces.

Code: Select all
`int main(){   int cases,caseno;   int p;      cases=read_number();   for(caseno=1;caseno<=cases;caseno++){      read_board();      for(p=1;p<=pieces;p++){         read_piece();         if(emptypiece) printf("Yes\n");         else if(emptyboard) printf("No\n");         else if(piece_fits_board()) printf("Yes\n");         else printf("No\n");         }      printf("\n");      }   return 0;   }`
It's accepted and it would answer 'Yes' for your input. But I don't accept any claims about the sanity of my solution.

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Can someone give me more test cases ? thanks !!

My program is still "Wrong Answer" and I have tested all test cases in the forum .
studying @ ntu csie
SRX
Learning poster

Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

input:
Code: Select all
`52 2 1.**.5 5 .............*...........4 4 6.*...**...*...*.4 4 .*...**...*...*.4 4 ....**...*......3 3*..*..*..2 2 *.**4 4.*...**...*..**.4 4  .....**..**.....4 4 1.*...***.*******3 3**.******3 3 1.........2 2..*.3 3 1....*....2 2....`

output:

Code: Select all
`YesYesYesYesYesNoNoYesNoYes`
navid_a2b
New poster

Posts: 10
Joined: Mon Oct 02, 2006 4:32 pm
Location: Tehran,Iran

little joey, My code is just like yours. In my function piece_fits_board() I do it justlike in a problem called "Graphical Editor". I traverse the board recursevely looking for a place to fit the piece. I search in all board, where there exists '*'.

I've tested all cases in this forum and my program works, but i keep WA.

I really don't know what to do more. Could someone that got AC in this problem give me the output for the following input and, give me some trick input output? Thank you very much!

1
3 3 1
..*
..*
***
4 4
..*.
..*.
***.
Regards,
[]'s
Andre

ferrizzi
New poster

Posts: 23
Joined: Thu Mar 30, 2006 5:42 pm
Location: Brazil

Well, I'm sad to say that there are cases in the input where the pieces are disconnected. I'll contact the judges about it and probably get it fixed. But for now, expect
Code: Select all
`15 5 1******...**.*.**...******5 5******...**.*.**...******`
for which the answer is Yes.

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Thanks to you , navid_a2b !!!!

Your first test case saved my program , haha !
studying @ ntu csie
SRX
Learning poster

Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Hello, sorry for posting my code but I have tested all these cases and they are fine. Any help will be just great!

Code: Select all
`Cut after AC.`

Best regards,

Yandry.

Maybe the test case that showed me my mistake could help somebody, this is it:

Code: Select all
`13 3 1**.**.**.3 3.*****...`

neno_uci
Experienced poster

Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Is there any input like this:
Code: Select all
`14 4 1.**.********.**.4 6*.**.***..****..***.**.*`

if there then what is the output?

A1
Experienced poster

Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm

My accepted code returns...

Output:
Code: Select all
`No`

Hope it helps.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

This is very strange... I've tried all of test cases in this thread and my output is right. Nevertheless, I still got WA... Why?

Code: Select all
`#include<stdio.h>#define MAX 101int main(){   int max_m,max_n,m,n,s;   int t,i,j,k,p,q;   char first=1,valid,trim;   char board[MAX][MAX],puzzle[MAX][MAX];   scanf("%d",&t);   while(t--)   {      scanf("%d %d %d",&max_m,&max_n,&s);      for(i=0;i<max_m;i++)         scanf("%s",board[i]);      (first)?first=0:printf("\n");      for(i=0;i<s;i++)      {         scanf("%d %d",&m,&n);         for(j=0;j<m;j++)            scanf("%s",puzzle[j]);         /* trim up */         for(j=0;j<m;j++)         {            for(trim=1,k=0;k<n;k++)               if(puzzle[j][k]=='*') { trim=0; j=m; break; }            if(trim)            {               for(p=0;p<m-1;p++)                  for(q=0;q<n;q++)                  puzzle[p][q]=puzzle[p+1][q];               j--; m--;            }         }         /* trim down */         for(j=m-1;j>=0;j--)         {            for(trim=1,k=0;k<n;k++)               if(puzzle[j][k]=='*') { trim=0; j=-1; break; }            if(trim) m--;         }         /* trim left */         for(k=0;k<n;k++)         {            for(trim=1,j=0;j<m;j++)               if(puzzle[j][k]=='*') { trim=0; k=n; break; }            if(trim)            {               for(q=0;q<n-1;q++)                  for(p=0;p<m;p++)                  puzzle[p][q]=puzzle[p][q+1];               k--; n--;            }         }         /* trim right */         for(k=n-1;k>=0;k--)         {            for(trim=1,j=0;j<m;j++)               if(puzzle[j][k]=='*') { trim=0; k=-1; break; }            if(trim) n--;         }         /* puzzle fits board? */         if(m>=max_m&&n>=max_n)         {            for(valid=1,j=0;j<max_m;j++)               for(k=0;k<max_n;k++)                  if(puzzle[j][k]=='*'&&board[j][k]!='*')                     valid=0;            if(valid) goto zap;         }         else if(m>=max_m)         {            for(k=0;k<=max_n-n;k++)            {               for(valid=1,q=0;q<n;q++)                  for(j=0;j<max_m;j++)                     if(puzzle[j][q]=='*'&&board[j][k+q]!='*')                        valid=0;               if(valid) goto zap;            }         }         else if(n>=max_n)         {            for(j=0;j<=max_m-m;j++)            {               for(valid=1,p=0;p<m;p++)                  for(k=0;k<max_n;k++)                     if(puzzle[p][k]=='*'&&board[j+p][k]!='*')                        valid=0;               if(valid) goto zap;            }         }         else         {            for(j=0;j<=max_m-m;j++)               for(k=0;k<=max_n-n;k++)               {                  for(valid=1,p=0;p<m;p++)                     for(q=0;q<n;q++)                        if(puzzle[p][q]=='*'&&board[j+p][k+q]!='*')                           valid=0;                  if(valid) goto zap;               }         }         zap: printf(valid ? "Yes\n" : "No\n");      }   }   return 0;   }`

razor_blue
New poster

Posts: 27
Joined: Mon Nov 27, 2006 4:44 am
Location: Indonesia

What would be the output for this kind of test case?

Code: Select all
`3 3 1**.*.*.**5 5**...*.............*...**`
arif_pasha
New poster

Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm

arif_pasha wrote:What would be the output for this kind of test case?

Code: Select all
`3 3 1**.*.*.**5 5**...*.............*...**`

Output from my Accepted code
Code: Select all
`No`

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am