10908 - Largest Square

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Shadekur Rahman
New poster
Posts: 1
Joined: Sun Dec 20, 2009 5:52 pm

Re:

Post by Shadekur Rahman » Mon Dec 21, 2009 3:31 am

I am getting wa with my code. Can anyone help me what is wrong with my code?
Here is my code..

#include<iostream>

using namespace std;

int main (void)
{
int t,check = 1;

char in[100][101];

int m,n,i,j,k,l,q,e;

int r1,c1,r2,c2,t1,t2,t3,t4;

char c;

int count = 3 ;

int lin[20][2] ;

int inc = 1 ;

cin >> t ;


while(t)
{
cin >> m >> n >> q;

c = getchar() ;


for( i = 0 ; i < m ; i++ )
{
gets( in ) ;

}

for( j = 0 ; j < q ; j++ )
{
cin >> k >> l;

lin[j][0] = k;

lin[j][1] = l;

}

cout << m << " " << n << " " << q << "\n";

for( k = 0 ; k < q ; k++ )
{
i = lin[k][0] ;

j = lin[k][1] ;





r2 = i - 1 ;



c2 = j + 1;

t4 = c2 ;

r1 = i + 1;



c1 = j - 1 ;

t3 = c1 ;

c = in[j] ;

while( check )
{
// check from lower corner character

for( e = 0 ; e < count ; e++ )
{
if( in[r1][c1] != c )
{

check = 0;

break ;
}

c1++ ;




}



c1 = t3 ;

t1 = r1 ;


for( e = 0 ; e < count ; e++ )
{
if( in[r1][c1] != c )
{

check = 0;

break ;
}

r1 -- ;


}



for( e = 0 ; e < count - 1 ; e++)
{
if( in[r2][c2] != c )
{
check = 0;

break;

}

c2--;

}

c2 = t4 ;

t2 = r2 ;

for( e = 0 ; e < count - 1 ; e++)
{
if( in[r2][c2] != c )
{
check = 0;

break;

}

r2++;

}

if ( check == 1)

inc += 2 ;


r1 = t1 + 1;

t3-- ;

c1 = t3 ;

if( (r1 >= m) || ( c1 < 0 ) )

check = 0 ;

r2 = t2 - 1 ;



t4 ++;

c2 = t4 ;
if( (r2 < 0) || ( c2 >= n ) )

check = 0 ;

count += 2 ;

}

check = 1 ;

count = 3 ;


cout << inc <<"\n";

inc = 1 ;

}


t -- ;
}

return 0;
}

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

10908 - Largest Square

Post by sazzadcsedu » Sat May 01, 2010 7:20 pm

Can someone post me some critical i/0???someone plz.I tested all i/o given in previous post.
But still wrong ans.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 10908 - Largest Square

Post by Imti » Fri Jul 29, 2011 9:08 am

After passing all the input found here in board,I was getting WA repeatedly..By working more on my algorithm I found my code breaks for following inputs..After fixing it I got Acc...:)
Hope this may help people getting WA..

Input

Code: Select all

3
7 7 1
aaaxaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
3 3
7 7 1
aaxaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
3 3
7 7 1
aaxaaaa
aaxaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
3 3
Output

Code: Select all

7 7 1
5
7 7 1
5
7 7 1
3

a100438a1302
New poster
Posts: 2
Joined: Fri Nov 16, 2012 5:23 pm

Re: 10908 - Largest Square

Post by a100438a1302 » Fri Nov 16, 2012 5:25 pm

I have tried all the test cases and still got a WA...

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main(){
	freopen("output.txt","w",stdout);
	int m,n,q,value[101][101],a,b,temp,cc;
	char s[101][101];
	scanf("%d", &cc);
	while(cc>0){
		scanf("%d %d %d", &n, &m, &q);
		memset(value,0,sizeof(value));
		for(int i=0;i<n;i++)
			scanf("%s", &s[i]);
		value[1][1]=1;
		for(int i=1;i<n+1;i++)
			for(int j=1;j<m+1;j++)
				if(i==1||j==1)
					value[i][j]=1;
				else if(s[i-1][j-1]==s[i-2][j-2]&&s[i-1][j-1]==s[i-2][j-1]&&s[i-2][j-2]==s[i-1][j-2])
					value[i][j]=min(value[i-1][j],min(value[i-1][j-1],value[i][j-1]))+1;
				else value[i][j]=1;
		printf("%d %d %d\n", n,m,q);
		for(int i=0;i<q;i++){
			temp=-1;
			scanf("%d %d", &a, &b);
			for(int j=1;j<value[a+1][b+1];j++)
				if((value[a+1+j-1][b+1+j-1]+1)!=value[a+1+j][b+1+j]){
					temp=j-1;
					break;
				}
			if(temp==-1)
				printf("%d",(value[a+1][b+1]-1)*2+1);
			else printf("%d", temp*2+1);
			if(!(cc==1&&i==q-1))
				printf("\n");
		}
		cc--;
	}
	return 0;
}

Can anyone tell me what's wrong or provide me with some test cases, please?

Thank you! :oops:

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10908 - Largest Square

Post by brianfry713 » Tue Nov 20, 2012 3:26 am

Don't write to a file.
Check input and AC output for thousands of problems on uDebug!

a100438a1302
New poster
Posts: 2
Joined: Fri Nov 16, 2012 5:23 pm

Re: 10908 - Largest Square

Post by a100438a1302 » Fri Nov 23, 2012 3:29 pm

I have tried but it still doesn't work...

any critical test cases for me? thank you!! :(

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10908 - Largest Square

Post by brianfry713 » Fri Nov 30, 2012 7:14 am

Print a newline at the end of the last line of the output.
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10908 - Largest Square

Post by uDebug » Mon Jun 16, 2014 3:07 pm

Replying to follow the thread.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 109 (10900-10999)”