题目简述
给定 \(N \times M\) 的字符矩阵，有 \(Q\) 次询问，对于每次询问给出 \(x,y\)，求以 \((x,y)\) 为中心的最大正方形边长且正方形中字符均相同。
思路
看到数据范围较小，可以考虑深搜解决，约掉常数的时间复杂度最坏为 \(O(q \times \min(n,m))\)，勉强可以通过。（不过代码跑的飞快，数据还是有点水的。）
考虑深搜的实现，以 \((x,y)\) 为中心开始搜，每次边长增加 \(2\)，即距 \((x,y)\) 的距离 \(d\) 每次增加 \(2\)。对于每次增加，判断四周的字符是否与中心 \((x,y)\) 相同，不相同终止搜索即可，记得每次增加完边长后，实时更新 \(ans\)！
下面是代码实现：
#include<iostream>
using namespace std;
#define MAXN 1005 // 数组大小。
int n, m, q, ans = 0, x, y; // 题目给定变量及辅助变量。
char mp[MAXN][MAXN]; // 存储字符矩阵。
// 开搜，传入中心坐标及距中心距离 date。
void dfs(int x, int y, int date) {
if(!(y - date >= 1 && y + date <= m && x - date >= 1 && x + date <= n)) return; // 出现越界，直接终止。
// 分别搜索上、下、左、右四个边。
for(int i = y - date; i <= y + date; i ++)
if(mp[x - date][i] != mp[x][y]) return;
for(int i = x - date; i <= x + date; i ++)
if(mp[i][y - date] != mp[x][y]) return;
for(int i = y - date; i <= y + date; i ++)
if(mp[x + date][i] != mp[x][y]) return;
for(int i = x - date; i <= x + date; i ++)
if(mp[i][y + date] != mp[x][y]) return;
ans = date * 2 + 1; // 更新 ans 的值。
dfs(x, y, date + 1); // 接着搜。
return;
}
int main() {
scanf("%d %d %d", &n, &m, &q);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
cin >> mp[i][j];
while(q --) {
scanf("%d %d", &x, &y);
x ++, y ++, ans = 1; // 因为题目中下边从 0 开始，所以都先自加 1，另外初始化 ans。
dfs(x, y, 1); // 深搜。
printf("%d\n", ans); // 输出答案，记得换行。
}
return 0;
}
\[\texttt{The End!}
\]