10908 Largest Squares

題目敘述

給定一個字元矩形，您必須找出最大正方形的邊的長度。 在其中正方形內的所有字元皆相同，並且正方形的中心(兩個對角線的交點)位於位置(r, c)。 矩形的高度和寬度分別為M和N。矩形的左上角座標為(0, 0)，右下角座標為(M-1, N-1)。

例如：給定中心位置(1, 2)，此最大正方形邊長為3。

abbbaaaaaa
abbbaaaaaa
abbbaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaccaaaaaa
aaccaaaaaa

輸入說明

輸入第一行為一個整數T (T < 21)，T代表有幾組測資。 每組測資的第一行包含三個整數M，N (1 <= M, N <= 100)，Q (Q < 21)。 其中M，N表示矩形的高度和寬度，Q代表詢問的數量。 接下來M行每行N個字元，代表輸入的字元矩形。 接下來Q行，每行包含兩個整數r和c。

輸出說明

對於每組測資。 第一行輸出M，N，Q值，以空格分開。 接下來Q行，輸出以(r, c)當中心所對應的最大正方形邊長。

解題思路

每次向左上方擴大一格掃，只要在範圍內有和中心點不同的字元就輸出上次掃的邊長，如果碰到邊界就停止，直接輸出

程式碼

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int n;
  cin>>n;
  while(n--)
  {
    int a,b,d;
    cin>>a>>b>>d;
    char arr[a][b];
    for(int i=0;i<a;i++)for(int j=0;j<b;j++)cin>>arr[i][j];
    cout<<a<<' '<<b<<' '<<d<<endl;
    while(d--)
    {
      int x,y,fx,fy,ex,ey,t=1,ans=1;
      cin>>x>>y;
      char carr=arr[x][y];
      while(1)
      {
        if(x-t>=0&&y-t>=0&&x+t<a&&y+t<b)fx=x-t,fy=y-t,ex=x+t,ey=y+t,t++;
        else break;
        for(int i=fx;i<=ex;i++)for(int j=fy;j<=ey;j++)if(arr[i][j]!=carr)break;
        ans+=2;
      }
      cout<<ans<<endl;
    }
  }
    return 0;
}