题目简述
给定 \(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!}
\]
标签:字符,int,题解,每次,MAXN,ans,date,P2427
From: https://www.cnblogs.com/So-noSlack/p/17736359.html