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

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Tue Feb 07, 2006 7:31 pm

What is your output for:
2
1 1 1
a
0 0
3 2 1
aa
aa
aa
1 1
Where's the "Any" key?

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Thu Feb 09, 2006 7:57 am

Code: Select all

1 1 1
1
3 2 1
1

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Thu Feb 09, 2006 6:44 pm

What about the following ??

Code: Select all

1
12 3 4
aab
aaa
aaa
baa
aaa
aaa
aaa
aaa
baa
aaa
aaa
aab
1 1
4 1
7 1
10 1

Code: Select all

12 3 4
1
1
1
1
Where's the "Any" key?

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Thu Feb 09, 2006 6:47 pm

What about the following ??

Code: Select all

1
12 3 4
aab
aaa
aaa
baa
aaa
aaa
aaa
aaa
baa
aaa
aaa
aab
1 1
4 1
7 1
10 1

Code: Select all

12 3 4
1
1
1
1
And if that passes too.... I am in short of ideas :P
Where's the "Any" key?

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Fri Feb 10, 2006 6:55 am

Well my prog matches the o/p exactly. Thanks for your patience, but I guess I'll have to give
up on this one :(

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sat May 20, 2006 10:57 pm

Emilio wrote:Maybe this test cases can be interesting:

Code: Select all

2
7 10 4
abbbaaaaaa
a bbaaaa a
abbbaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaccaaaaaa
aaccaaaaaa
1 2
2 4
4 6
5 2
1 1 1
a
7 8
I am not sure if such an input is legal. I think there should be no spaces in the grid. At least my AC would abort() on such an input.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sat May 20, 2006 10:59 pm

Solaris wrote:And if that passes too.... I am in short of ideas :P
If nothing helps, try to post your code here. Maybe, I (or somebody else) will have time to find the bug.

MajidIust
New poster
Posts: 4
Joined: Sun Jul 10, 2005 9:19 pm
Contact:

10908

Post by MajidIust » Tue Aug 15, 2006 2:45 am

i dont know what i get wa.

Code: Select all

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector <int > out;
char treasure[101][101];
int solve(int M,int N,int R,int C)
{
	int left,right,top,down;
	int TR,TC;
	int maxV,maxH;
	int diffV,diffH,diff;
	int Bound;
	int Result = 1;
	bool flag; 
	TR = R;
	while(R--)
		if(treasure[R][C] == treasure[TR][C])
			top = R;
		else
			break;
	R = TR;
	TC = C;
	while(C--)
		if(treasure[R][C] == treasure[R][TC])
			left = C;
		else
			break;
	C = TC;
	TR = R;
	while(R++ < M)
		if(treasure[R][C] == treasure[TR][C])
			down = R;
		else
			break;
	R = TR;
	TC = C;
	while(C++ < N)
		if(treasure[R][C] == treasure[R][TC])
			right = C;
		else
			break;
	C = TC;
	maxV = min(top,down);
	maxH = min(left,right);
	diffV = abs(R-maxV);
	diffH = abs(C-maxH);
	diff = min(diffH,diffV);
	for(int i=1;i<=diff;i++)
	{
		flag = true;
		for(int j=-i;j<=i;j++)
		{
			for(int k=-i;k<=i;k++)
				if(treasure[R][C] != treasure[R+j][C+k])
				{
					flag = false;
					break;
				}
			if(!flag)
				break;
		}
		if(!flag)
			break;
		Result+=2;
	}	
	return Result;
}
void Print(int N)
{
	cout << N << endl;
}

int main()
{
	int M,N,Q,T,Answer,R,C,TQ;
	cin >> T;
	while(T--)
	{
		cin >> M >> N >> Q;
		for(int i=0;i<M;i++)
			for(int j=0;j<N;j++)
				cin >> treasure[i][j];
		TQ = Q;
		while(Q--)
		{
			cin >> R >> C;
			Answer = solve(M,N,R,C);
			out.push_back(Answer);
		}
		cout << M << " " << N << " "  << TQ << endl;
		for_each(out.begin (),out.end(),Print);
		out.clear ();
		cout << endl;
	}
	return 0;
}

Thanks.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10908

Post by Martin Macko » Tue Aug 15, 2006 11:21 am

MajidIust wrote:i dont know what i get wa.
Thanks.
Check this one:

Code: Select all

2
9 10 1
qqqqqqqqqW
UUUUqqqqqK
JJJJJZZZZZ
JJJNNNNNNN
JqqNNNNNNN
JqqNNNNNNN
JJJJJJJJJe
qejjjjQQQQ
OOOOOOOQQQ
1 0
2 17 1
JJJJJJJJJJUUUBvsM
JJJJJJJJJJCCCggmx
1 3
The correct output:

Code: Select all

9 10 1
1
2 17 1
1
You output 3 in the second case.

MajidIust
New poster
Posts: 4
Joined: Sun Jul 10, 2005 9:19 pm
Contact:

Thanks.

Post by MajidIust » Tue Aug 15, 2006 4:42 pm

so thanks, i make a very ... mistake.i get AC.[/i]

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: Thanks.

Post by Martin Macko » Tue Aug 15, 2006 8:30 pm

MajidIust wrote:so thanks, i make a very ... mistake.i get AC.
After getting AC, please, remove the code from your previous post, so there won't be too many spoilers here :wink:

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 10908 - Largest Square

Post by Chirag Chheda » Sat Sep 06, 2008 10:08 am

Can someone please help me on this question. I dont know where is the bug in my solution.The judge always shows WA though i have passed all the test cases posted here in the forum.

Code: Select all

#include<iostream>

using namespace std;

int main()
{
    int t,m,n,q,i,j,k,x,y;
    char c;
    bool f;
    scanf("%d",&t);
    
    while(t--)
    {
         scanf("%d %d %d",&m,&n,&q);
         printf("%d %d %d\n",m,n,q);
         char arr[m][n];
         
         for(i=0;i<m;i++)
         for(j=0;j<n;j++)
         cin>>arr[i][j];
         
         while(q--)
         {
                scanf("%d %d",&x,&y);
                c=arr[x][y];
                j=1;
                
                if((x>=n || x<0) && (y<0 || y>=n))
                {
                printf("0\n");
                continue;
                }
                
                while(y-j>=0 && y+j<n && x-j>=0 && x+j<n)
                {
                       f=0;
                       for(i=y-j,k=x-j;i<=y+j;i++,k++)
                       {
                           if(!(arr[x-j][i]==c && arr[x+j][i]==c && arr[k][y-j]==c && arr[k][y+j]==c))
                           {
                           f=1;
                           break;
                           }
                       }
                       
                       if(f==1)
                       break;
                       
                       j++;
                }
                printf("%d\n",(j-1)*2+1);
         }
    }
    return 0;
}
Thanking u in advance.
Waiting 4 a reply

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 10908 - Largest Square

Post by Chirag Chheda » Mon Sep 15, 2008 9:54 am

Can someone plz reply or post some input output data so that i can check my code..

thnx in advance!!

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 10908 - Largest Square

Post by Chirag Chheda » Mon Sep 22, 2008 8:04 am

Plz help me.. I am unable 2 get an ACC for this simple problem.
Any help is appreciated.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10908 - Largest Square

Post by Jan » Sat Mar 07, 2009 12:59 am

Code: Select all

char arr[m][n];
So, you are declaring a character 2d array. Now, when we take a string, there is an extra null character at the end. So, at least a[m][n+1] is needed. Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 109 (10900-10999)”