## 10504 - Hidden squares

Moderator: Board moderators

saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Contact:

### 10504 - Hidden squares

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
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
- - B -
B - - -
- - - B
- B - -
-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Contact:

-sohel

sunhong
New poster
Posts: 19
Joined: Sat Apr 12, 2003 6:13 pm
Location: China

### 10504-Can anyone give me some hint?

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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

### Re: 10504-Can anyone give me some hint?

sunhong wrote:... 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
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan
I have forgot which method I use for it.

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am
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
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm
My AC program for 100 x 100 square of capital A's gives:

8332500

Wojciech

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

### 10504

deleted
Last edited by asif_rahman0 on Sat May 26, 2007 11:28 pm, edited 1 time in total.

ThanhNhan
New poster
Posts: 15
Joined: Sun Aug 08, 2004 12:24 am
you need to check the bounds of the indexes for word[k+l-j][l-k+i]

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

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 <---- ?

Last edited by x140l31 on Tue May 15, 2007 1:21 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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``````
Ami ekhono shopno dekhi...
HomePage

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am
thx Jan I got AC

MrBlah
New poster
Posts: 2
Joined: Tue May 15, 2007 4:18 am
Location: Shilito

### WA!

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!??
ARG!

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