P6504题解

nfls20200418 · 2021-07-16 15:52:36 · 题解

注意：本题解非原创，源于官方题解。

思路

• 这是一道几何题，总体还是有难度的。(废话少说)

• 让我们用 M 表示完全包含所提供多边形的具有最小面积的矩形。我们用尽可能少的垂直线与 M 相交，使其中一条线穿过每个多边形顶点。直线将多边形分割成矩形，因此其面积可以计算为各个矩形的面积之和。请注意，单个矩形的面积可以使用包含排除原理计算。面积等于上下边缘以上的面积之差。

• 此外，它们的面积之和可以通过逆时针遍历多边形来获得。每当我们遍历一条水平边时，我们就把它上面的区域加到总和上，符号取决于遍历的方向。由于最上面的边将从右向左遍历，因此我们将在该方向添加带负号的区域。

• 让我们从表中选择一个单元格作为矩形 M 的左上角。接下来，我们确定 M 指定的多边形中包含的一个单元上的一个字母。只有当多边形的所有单元都包含同一个字母时，即如果该字母的发生次数等于其面积，则多边形才是单块体。

• 一个字母在多边形内的入射次数可以用与计算其面积类似的方法来计算。唯一的区别是，我们没有添加区域，而是添加所需字母的发生次数。矩阵可以预先计算包含数据，使我们能够在固定时间内回答这样的查询。

• 最后，通过对表中每个可能的左上角单元运行所描述的算法来获得单块多边形的总数。时间复杂度为 O(R*C*V)。

AC代码

```cpp
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 510;
const int MAXV = 510;

struct point {
    int x, y;
    point() {}
    point (int _x, int _y) { 
        x = _x, y = _y; 
  }
} pts[MAXV];

int R, C, V;
char mat[MAXN][MAXN];
int sum[MAXN][MAXN][26];

int area() {
    int ret = 0;

    point cur = pts[0];
    for (int i = V - 1; i >= 0; --i) {
        point nxt = pts[i];
        if (cur.y != nxt.y)
            ret += (nxt.y - cur.y) * cur.x;
        cur = nxt;
  }

    return ret;
}

int cnt(int row, int col, int letter) {
    int ret = 0;

    point cur = pts[0];
    for (int i = V - 1; i >= 0; --i) {
        point nxt = pts[i];
        if (cur.y != nxt.y) 
            ret += sum[nxt.x + row][nxt.y + col][letter] - sum[cur.x + row][cur.y + col][letter];
    cur = nxt;
  }

    return ret;
}

int main(void) {

    scanf("%d %d", &R, &C);
    for (int row = 0; row < R; ++row)
        scanf("%s", mat[row]);

    for (char letter = 0; letter < 26; ++letter) 
        for (int row = 1; row <= R; ++row)
            for (int col = 1; col <= C; ++col)
                sum[row][col][letter] = (mat[row - 1][col - 1] == 'a' + letter) +
                sum[row - 1][col][letter] + 
                sum[row][col - 1][letter] - 
                sum[row - 1][col - 1][letter];

    int min_row = R;
    int max_row = 0;
    int min_col = C;
    int max_col = 0;

    scanf("%d", &V);

    for (int i = 0; i < V; ++i) {
        scanf("%d %d", &pts[i].y, &pts[i].x);
        min_row = min(min_row, pts[i].x);
        max_row = max(max_row, pts[i].x);
        min_col = min(min_col, pts[i].y);
        max_col = max(max_col, pts[i].y);
    }

    max_row -= min_row;
    max_col -= min_col;

    for (int i = 0; i < V; ++i) {
        pts[i].x -= min_row;
        pts[i].y -= min_col;
    }

    int A = area();
    point p(min_row, C);
    for (int i = 0; i < V; ++i) 
        if (pts[i].x == min_row) p.y = min(p.y, pts[i].y);

    int ret = 0;

    for (int row = 0; row + max_row <= R; ++row)
        for (int col = 0; col + max_col <= C; ++col) {
            int letter = mat[p.x + row][p.y + col] - 'a';
            int n = cnt(row, col, letter);
            ret += n == A;
    }

    printf("%d\n", ret);
} 

To err is human, to forgive divine.