自动搬运

查看原文

来自洛谷，原作者为

	Link_Cut_Y 菜就多练

搬运于2025-08-24 21:37:35，当前版本为作者最后更新于2021-12-04 11:29:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门

• 题目分析：

  在一个仅有小写字母组成的矩阵中，规定源点 $(x, y)$，求一个满足以下条件的正方形的最大边长是多少。

  正方形需要满足的条件：

  1. 正方形的边长为整数（废话）。
  2. 在整个正方形中，包含且只包含一种小写字母。
  3. 正方形的中心为$(x, y)$
  4. 正方形中的四个顶点都不超过矩阵的边缘。（在矩阵内部）

  题目有多组数据。

• 做法分析：

  Tips: 请先了解二维前缀和

  暴力做法：

  int res = 1;
  for (int i = 1; i <= l; i ++ )
  {
     int tx = x + i, ty = y + i;
     int fx = x - i, fy = y - i; // 枚举起点和终点的横纵坐标
     for (int w = 0; w < 26; w ++ ) // 循环枚举每个小写字母 
     {
         int cnt = 0;
         for (int j = fx; j <= tx; j ++ ) 
             for (int k = fy; k <= ty; k ++ ) // 循环遍历整个正方形 
                 if (g[j][k] - 'a' == w) cnt ++ ;
  
         if (cnt == (tx - fx + 1) * (tx - fx + 1)) res = max(res, tx - fx + 1); // 如果整个正方形内有且只有 w + 'a' 这一种小写字母，那么更新答案 
     }
  }
  

  时间复杂度：无法估计的高（是我不会算）

  现在我们来看一下，基于暴力做法，怎样才能优化一下这个问题;

  第一层循环——没什么好改的。 第二、三、四层循环...... 没错，就是二维前缀和！ 我们用一个 $s[x, y, k]$ 数组来记录从 $(1, 1)$ 到 $(x, y)$ 中字符 $k$ 出现的次数, 然后，我们的 $cnt$ 就不需要使用两层循环来计算了

  $cnt = s[x + i][y + i][type] - s[x - i - 1][y + i][type] - s[x + i][y - i - 1][type] + s[x - i - 1][y - i - 1][type];$

  （其中$x, y, type$ 分别表示源点的横坐标，源点的纵坐标，源点的小写字母是什么，$x + i, y + i, x - i, y - i$ 分别表示正方形右上顶点的横、纵坐标， 左下顶点的横、纵坐标）

  代码如下：

      int type = g[x][y] - 'a', res = 1;
      int l = min(min(n - x, x - 1), min(m - y, y - 1));
      if (l == 0) return 1;
  
      for (int i = 1; i <= l; i ++ )
      {
          int cnt = s[x + i][y + i][type] - s[x - i - 1][y + i][type] - s[x + i][y - i - 1][type] + s[x - i - 1][y - i - 1][type];
          if (cnt == (2 * i + 1) * (2 * i + 1)) res = max(res, 2 * i + 1);
          else break;
      }
      return res;
  

• Coding

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1010;
char g[N][N];
int s[N][N][26];
int n, m, T;

void init()
{
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= m; j ++ )
			for (int k = 0; k < 26; k ++ )
				s[i][j][k] = s[i - 1][j][k] + s[i][j - 1][k] - s[i - 1][j - 1][k] + (g[i][j] - 'a' == k ? 1 : 0);
}

int Biggest_square(int x, int y)
{
	int type = g[x][y] - 'a', res = 1;
	int l = min(min(n - x, x - 1), min(m - y, y - 1));
	if (l == 0) return 1;
	
	for (int i = 1; i <= l; i ++ )
	{
		int cnt = s[x + i][y + i][type] - s[x - i - 1][y + i][type] - s[x + i][y - i - 1][type] + s[x - i - 1][y - i - 1][type];
		if (cnt == (2 * i + 1) * (2 * i + 1)) res = max(res, 2 * i + 1);
		else break;
	}
	return res;
}

int main()
{
	scanf("%d%d%d", &n, &m, &T);
	
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= m; j ++ )
			cin >> g[i][j];
	
	init();
	while (T -- )
	{
		int x, y;
		scanf("%d%d", &x, &y);
		x += 1, y += 1;
		printf("%d\n", Biggest_square(x, y));
	}
	
	return 0;
}