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.