题解 P2427 【Wave】

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