11140 - Little Ali's Little Brother!

[emotional blind]

Yes

[ferrizzi]

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: Select all

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

int numCasos, N, M, S, n, m, cont, total;
char grid[MAX][MAX], bloco[MAX][MAX], visitado[MAX][MAX];

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);
	  visitado[iG][jG]=1;
	  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

[little joey]

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.

About your question: my main looks like this:

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.

[SRX]

Can someone give me more test cases ? thanks !!

My program is still "Wrong Answer" and I have tested all test cases in the forum .

[navid_a2b]

input:

Code: Select all

5

2 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

Yes

Yes
Yes
Yes
Yes
No
No

Yes

No

Yes

[ferrizzi]

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
..*.
..*.
***.

[little joey]

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

1
5 5 1
*****
*...*
*.*.*
*...*
*****
5 5
*****
*...*
*.*.*
*...*
*****

for which the answer is Yes.

[SRX]

Thanks to you , navid_a2b !!!!

Your first test case saved my program , haha !

[neno_uci]

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

1
3 3 1
**.
**.
**.
3 3
.**
***
...

And the answer is No.

[A1]

Is there any input like this:

Code: Select all

1

4 4 1
.**.
****
****
.**.

4 6
*.**.*
**..**
**..**
*.**.*

if there then what is the output?

[Jan]

My accepted code returns...

Output:

Code: Select all

No

Hope it helps.

[razor_blue]

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 101
int 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;	
}

Someone please help me...

[arif_pasha]

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

Code: Select all

3 3 1
**.
*.*
.**
5 5
**...
*....
.....
....*
...**

[emotional blind]

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