10908 - Largest Square

[Solaris]

What is your output for:

2
1 1 1
a
0 0
3 2 1
aa
aa
aa
1 1

[sumankar]

Code: Select all

1 1 1
1
3 2 1
1

[Solaris]

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

[Solaris]

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

[sumankar]

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

[Martin Macko]

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.

[Martin Macko]

And if that passes too.... I am in short of ideas

If nothing helps, try to post your code here. Maybe, I (or somebody else) will have time to find the bug.

[MajidIust]

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.

[Martin Macko]

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]

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

[Martin Macko]

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

[Chirag Chheda]

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]

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

thnx in advance!!

[Chirag Chheda]

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

[Jan]

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.