K - King's Children

题意

给一个矩形， 矩形里有一些不同的字母，其他都是空地，每个字母会占据一个矩形区域，要求构造一种方案，把所有的空地都划分掉，并且使 'A' 所占的区域面积最大

思路

第一步， 找 A 的最大矩形

先找到 'A' 的最大矩形，我们可以这样做， 先把 'A' 所在的地方进行列上的扩展， 设 'A' 的坐标是 (x, y)

设两个数组 l[N], r[N]。 l[row] 表示以 (x, y) 和 (row, y) 作为底边，最多能向左边扩展多少个单位长度， r[row] 表示以 (x, y) 和 (row, y) 作为底边， 最多向右扩展多少个单位长度。

这样， 我们可以枚举这个矩形的上界 up 和下界 down

则这个矩形的高是 down - up + 1 , 长是 (min(l[up], l[down]) + min(r[up], r[down]) + 1)

第二步， 完成剩余字母的合法构造

如果用第一步的方法去填剩下的字母， 可能无法填完所有的空位。

把剩下的区域分成如下四个部分

对于绿色部分，可以按列填充，对于每一个字母，尽可能的向向下扩充，若一列都没有字母，则向 'A' 方向的列进行复制。

蓝色的部分，进行按行填充。

这样能保证构造出一个合法的方案。

/*
 * @Author: zhl
 * @LastEditTime: 2021-03-02 21:31:19
 */

#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
typedef long long ll;
int n, m;

char mp[N][N];
int l[N], r[N];

void solve(int x, int y) {
    char c = mp[x][y] - 'A' + 'a';
    for (int i = 1;i <= n;i++)l[i] = r[i] = 0;

    for (int i = x;i <= n;i++) {
        if (i != x and mp[i][y] != '.')break;
        while (y + r[i] + 1 <= m and mp[i][y + r[i] + 1] == '.')r[i]++;
        while (y - l[i] - 1 >= 1 and mp[i][y - l[i] - 1] == '.')l[i]++;
        if (i != x)l[i] = min(l[i], l[i - 1]), r[i] = min(r[i], r[i - 1]);
    }
    for (int i = x - 1;i >= 1;i--) {
        if (mp[i][y] != '.')break;
        while (y + r[i] + 1 <= m and mp[i][y + r[i] + 1] == '.')r[i]++;
        while (y - l[i] - 1 >= 1 and mp[i][y - l[i] - 1] == '.')l[i]++;
        l[i] = min(l[i], l[i + 1]), r[i] = min(r[i], r[i + 1]);
    }
    int up, down, now = l[x] + r[x] + 1;
    up = down = x;
    for (int i = x;i >= 1;i--) {
        if (i != x and mp[i][y] != '.')break;
        for (int j = x;j <= n;j++) {
            if (j != x and mp[j][y] != '.')break;
            int S = (min(l[i], l[j]) + min(r[i], r[j]) + 1) * (j - i + 1);
            if (S > now) {
                now = S;up = i;down = j;
            }
        }
    }

    for (int i = up;i <= down;i++) {
        for (int j = y - min(l[up], l[down]);j <= y + min(r[up], r[down]);j++) {
            if (i != x or j != y)mp[i][j] = c;
        }
    }

    for (int j = y - min(l[up], l[down]) - 1;j >= 0;j--) {
        int cnt = 0;
        for (int i = 1;i <= n;i++) {
            if (mp[i][j] > 'A' and mp[i][j] <= 'Z') {
                char c = mp[i][j] - 'A' + 'a';
                int k = 1;
                while (i - k >= 1 and mp[i - k][j] == '.')mp[i - k][j] = c, k++;
                k = 1;
                while (i + k <= n and mp[i + k][j] == '.')mp[i + k][j] = c, k++;
                cnt++;
            }
        }
        if (cnt == 0) {
            for (int i = 1;i <= n;i++)mp[i][j] = tolower(mp[i][j + 1]);
        }
    }

    for (int j = y + min(r[up], r[down]) + 1;j <= m;j++) {
        int cnt = 0;
        for (int i = 1;i <= n;i++) {
            if (mp[i][j] > 'A' and mp[i][j] <= 'Z') {
                char c = mp[i][j] - 'A' + 'a';
                int k = 1;
                while (i - k >= 1 and mp[i - k][j] == '.')mp[i - k][j] = c, k++;
                k = 1;
                while (i + k <= n and mp[i + k][j] == '.')mp[i + k][j] = c, k++;
                cnt++;
            }
        }
        if (cnt == 0) {
            for (int i = 1;i <= n;i++)mp[i][j] = tolower(mp[i][j - 1]);
        }
    }

    for (int i = up - 1;i >= 1;i--) {
        int cnt = 0;
        for (int j = y - min(l[up], l[down]);j <= y + min(r[up], r[down]);j++) {
            if (mp[i][j] > 'A' and mp[i][j] <= 'Z') {
                char c = mp[i][j] - 'A' + 'a';
                int k = 1;
                while (j - k >= y - min(l[up], l[down]) and mp[i][j - k] == '.')mp[i][j - k] = c, k++;
                k = 1;
                while (j + k <= y + min(r[up], r[down]) and mp[i][j + k] == '.')mp[i][j + k] = c, k++;
                cnt++;
            }
        }
        if(cnt == 0){
            for (int j = y - min(l[up], l[down]);j <= y + min(r[up], r[down]);j++) mp[i][j] = tolower(mp[i + 1][j]);
        }
    }

    for (int i = down + 1;i <= n;i++) {
        int cnt = 0;
        for (int j = y - min(l[up], l[down]);j <= y + min(r[up], r[down]);j++) {
            if (mp[i][j] > 'A' and mp[i][j] <= 'Z') {
                char c = mp[i][j] - 'A' + 'a';
                int k = 1;
                while (j - k >= y - min(l[up], l[down]) and mp[i][j - k] == '.')mp[i][j - k] = c, k++;
                k = 1;
                while (j + k <= y + min(r[up], r[down]) and mp[i][j + k] == '.')mp[i][j + k] = c, k++;
                cnt++;
            }
        }
        if (cnt == 0) {
            for (int j = y - min(l[up], l[down]);j <= y + min(r[up], r[down]);j++) mp[i][j] = tolower(mp[i - 1][j]);
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1;i <= n;i++)scanf("%s", mp[i] + 1);
    for (int i = 1;i <= n;i++)for (int j = 1;j <= m;j++) if (mp[i][j] == 'A')solve(i, j);


    for (int i = 1;i <= n;i++)printf("%s\n", mp[i] + 1);

}