10504 - Hidden squares

[saiqbal]

i don't understand the 2nd sample input. i found only 7 squares for B in the following grid, but sample output says there are 8.

Code: Select all

A	B	B	A
B	B	B	B
A	B	B	B
A	B	B	A

the squares i found for B are:

Code: Select all

1.
-	B	B	-
-	B	B	-
-	-	-	-
-	-	-	-

2.
-	-	-	-
-	B	B	-
-	B	B	-
-	-	-	-

3.
-	-	-	-
-	-	-	-
-	B	B	-
-	B	B	-

4.
-	-	-	-
-	-	B	B
-	-	B	B
-	-	-	-

5.
-	B	-	-
B	-	B	-
-	B	-	-
-	-	-	-

6.
-	-	B	-
-	B	-	B
-	-	B	-
-	-	-	-

7.
-	-	-	-
-	-	B	-
-	B	-	B
-	-	B	-

can someone please tell me where is the 8th square?

-sohel

[turuthok]

- - B -
B - - -
- - - B
- B - -

-turuthok-

[saiqbal]

thanx.. that was really helpful

-sohel

[sunhong]

I think about this problem for a long time. But I can't find good method to solve it. I'm afraid to get time limit excceed if I check every possible square. Can someone introduce how to solve it? Thank you!

[little joey]

... I'm afraid to get time limit excceed if I check every possible square. ...

You'll never know if you don't try...

[Ghost77 dimen]

I have forgot which method I use for it.

But about O(n^4), pass it with not bad speed.

[WR]

If the input consists of an 100 x 100 grid with just capital A's. How many squares are there?

My program returns 10551500.

Is that correct?

[w k]

My AC program for 100 x 100 square of capital A's gives:

8332500


Wojciech

[asif_rahman0]

deleted

[ThanhNhan]

you need to check the bounds of the indexes for word[k+l-j][l-k+i]

[x140l31]

One question about this problem.

I had Wrong Answer:

Code: Select all

AC code

I think that the problem should be in the ooutput. I which order I have to write it?



In the input, after the "n lines" of the "square", what we have to do with the "letters"?

Sample Input

3

2

AAA

AAA

BAB

A <---- ?

B <---- ?

Sorry about my bad english '

[Jan]

Check the cases caryfully. Hope these help.

Input:

Code: Select all

3
2 
AAA
AAA
BAB
B
A
4
2
ABBA
BBBB
ABBB
ABBA
A
B
0

Output:

Code: Select all

B 0
A 3

A 1
B 8

[x140l31]

thx Jan I got AC

[MrBlah]

Code: Select all

#include <stdio.h>
#include <string.h>

int main (){
	int largo, x, y, q, p, n[26], cantletras, i, j, K;
	char w[101][101],a[26];

	while(scanf("%d", &largo)==1){
		if (largo <= 0 || largo > 100) return 0;

		getchar();
		scanf("%d", &cantletras);
		getchar();

		for (i=0;i<26;i++) n[i]=0;

		for (i=0;i<largo;i++){
			scanf("%s", w[i]);
			getchar();
			K = strlen(w[i]);
			w[i][K]='\0';
		}
		
		for (i=0;i<cantletras;i++){
			scanf("%c", &a[i]);
			getchar();
		}

		for (x=0; x<largo; x++)
		{
			for (y=0;y<largo;y++)
			{
				for (q=0; q<largo;q++)
				{
					for (p=1; p<largo; p++) 
					{
						if ( (x+p+q<largo) && (x+p+q-p<largo) && (x+p+q-p>=0) && (y-q>=0) && (y-q+p<largo) && (y-q+p>=0) && (y-q+p+q<largo) && (y-q+p+q>=0) && (w[x][y] == w[x+p][y-q]) && (w[x+p][y-q] == w[x+p+q][y-q+p]) && (w[x+p+q][y-q+p] == w[x+p+q-p][y-q+p+q]))
						{
							for (j=0; j<26; j++) 
							{
								if (a[j] == w[x][y])
								{
									++n[j];
									break;
								}
							}
						}
					}
				}
			}
		}
		
		for (j=0;j<cantletras;j++){
			printf("%c %d\n", a[j],n[j]);
		}
		printf("\n");
	}
	return 0;
}

I keep getting WA and i tested all the test casesin the board and got all of them right T_T WHY WA!??

[Jan]

You have to print a blank line between two consecutive cases, not after every case.