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;
}