https://www.luogu.com.cn/problem/P6504这道题和扫描线的关系就是鱼和自行车的关系。二维前缀和求多边形面积格林公式该写的都在代码里了。// 注释 by proMatheus(hansang)有错指出 #includebits/stdc.h using namespace std; const int N 510; int R, C; char mat[N][N]; int sum[N][N][30]; int V; struct node { int x, y; } pos[N]; // 多边形顶点数组 int get_area(int r, int c, int let) { // 得到多边形按 (r, c) 偏移后面积内 let 字母的个数 // 当 let 26 时得到的是多边形的面积 int res 0; node pre pos[1]; // 按逆时针遍历所有边 // 顺时针面积会变成负的待会再将 for (int i V; i 1; i --) { node nxt pos[i]; if (nxt.y ! pre.y) { // 只有竖直边才贡献 res sum[nxt.x r][nxt.y c][let] - sum[pre.x r][pre.y c][let]; // 核心就是遇到竖直边 // 用后一个点到原点左上角矩形总值 - 前一个点到原点的矩形总值 // 自己拿样例模拟一下就懂了 // 这方法好像还挺常用的O(N) 求轴点多边形面积 // 关于为什么不能顺时针 // 我们要保证矩形最下面的横着的边nex 在右边点pre 在左边点 // 这是全局影响 res 最大的一次计算这次加的是不是负数决定了整个 res 的正负 // 只有逆时针能保证以上条件 } pre nxt; } return res; } int main () { ios::sync_with_stdio(false); cin.tie(0); cin R C; for (int i 0; i R; i ) { cin mat[i]; // 读入字母矩阵 } memset(sum, 0, sizeof(sum)); for (int let 0; let 26; let ) { for (int i 1; i R; i ) { for (int j 1; j C; j ) { int flag (mat[i - 1][j - 1] a let); if (let 26) { flag 1; // let [0, 25] 对应 [a, z] // 当 let 26 时计算的是整个矩形的面积 // 所以和字母无关flag 恒为 1 } sum[i][j][let] flag sum[i - 1][j][let] sum[i][j - 1][let] - sum[i - 1][j - 1][let]; // 将 based-0 的字母矩阵转为 based-1 的二维前缀和矩阵 } } } int mnr R, mxr 0; int mnc C, mxc 0; cin V; for (int i 1; i V; i ) { cin pos[i].y pos[i].x; // 这个阴 b读入顺序竟然是先 y 后 x mnr min(mnr, pos[i].x); mxr max(mxr, pos[i].x); mnc min(mnc, pos[i].y); mxc max(mxc, pos[i].y); } // 接下来将多边形平移到以 (0,0) 为原点 // 这样多边形就变成了相对坐标方便后续平移 mxr - mnr; mxc - mnc; for (int i 1; i V; i ) { pos[i].x - mnr; pos[i].y - mnc; } node p {mnr, C}; for (int i 1; i V; i ) { // 找到 mnr 行上最小的列坐标 if (pos[i].x mnr) { p.y min(p.y, pos[i].y); } } // 求得 p 是多边形左上角的点这个点作为参考点 // 平移时保证多边形内所有格子的字母都和参考点字母一样 int ans 0; int A get_area(0, 0, 26); // 多边形覆盖的总格子数 for (int i 0; i mxr R; i ) { for (int j 0; j mxc R; j ) { // 因为 pos 里存的多边形点都以 (0,0) 为原点 // 现在枚举 (i, j) 作为多边形平移的偏移量 int let mat[p.x i][p.y j] - a; // 那么 (p.x i, p.y j) 就是平移后的参考点 int res get_area(i, j, let); ans (res A) ? 1 : 0; } } cout ans \n; return 0; }