// 注释 by proMatheus(hansang)，有错指出 
#include<bits/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;
} 

这题看上去就很 USACO。比较套路，但编码比较注重细节。主要讲解扫描线分解法，并介绍一下格点积分法。

题目大意

给定一个 $r \times c$ 的由小写字母组成的矩阵。给定一个顶点在方格顶点上的、仅含直角的正交多边形。求该多边形在矩阵上有多少种仅通过平移得到的放置方式，可以使得多边形内部的字母全部相同。

解题思路

直接枚举左上角并逐一统计多边形内部点的情况，编码难度大且时间复杂度不可接受。

我们很容易可以想到用二维前缀和来判断一个矩形内字母的情况。

可是多边形处理起来比较复杂，于是先随便画一个多边形看看：

有没有发现什么。似乎我们总是可以把这个不规则的多边形分解成 $V/2 - 1$ 个横着的矩形。

于是，我们就可以通过二维前缀和快速地计算出由多个矩形组成的多边形信息。分解矩形我们可以用到扫描线分解法。

扫描线分解法

步骤如下：

1. 收集多边形所有顶点的 $y$ 坐标，进行排序并去重。
2. 枚举相邻的两根扫描线 $y_i$ 和 $y_{i+1}$，这两根线将整个平面切成了若干个水平的“带状区域”。
3. 遍历多边形所有的垂直边，看哪些边横跨了这个带状区域（即边的 $y$ 范围包含了 $[y_i, y_{i+1}]$），收集它们的横坐标。
4. 把这些垂直边的 $x$ 坐标从小到大排序。
5. 配对连点成面，排好序的 $x$ 坐标一定是成对出现的（可结合上图思考）。
6. 每一对 $[x_{2k}, x_{2k+1}]$ 与当前的 $[y_i, y_{i+1}]$ 就生成了一个标准的矩形。

接下来只需要枚举多边形区域的左上角，统计多边形内相同的字母数量是否与多边形面积相同就可以了。

代码实现

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

const int N = 505;

int R, C, V;
char g[N][N];
int s[26][N][N];

// 二维前缀和查询函数
inline int query(int id, int r1, int c1, int r2, int c2) {
    if (r1 > r2 || c1 > c2) return 0;
    return s[id][r2][c2] - s[id][r1 - 1][c2] - s[id][r2][c1 - 1] + s[id][r1 - 1][c1 - 1];
}

struct Rt { int xa, ya, xb, yb; };
vector<Rt> rs;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> g[i][j];
            int c = g[i][j] - 'a';
            for (int k = 0; k < 26; k++)
                s[k][i + 1][j + 1] = s[k][i][j + 1] + s[k][i + 1][j] - s[k][i][j] + (k == c);
        }
    }
    
    cin >> V;
    vector<pair<int, int>> p(V);
    int minx = N, miny = N, maxx = 0, maxy = 0;
    vector<int> sy;
    for (int i = 0; i < V; i++) {
        cin >> p[i].first >> p[i].second;
        minx = min(minx, p[i].first); maxx = max(maxx, p[i].first);
        miny = min(miny, p[i].second); maxy = max(maxy, p[i].second);
        sy.push_back(p[i].second);
    }
    sort(sy.begin(), sy.end());
    sy.erase(unique(sy.begin(), sy.end()), sy.end());
    
    // 预处理为以区域左上角为 (0,0) 的相对坐标
    for (auto &r : p) { r.first -= minx; r.second -= miny; }
    int W = maxx - minx, H = maxy - miny;
    
    // 扫描线分解
    for (int i = 0; i < (int)sy.size() - 1; i++) {
        int r1 = sy[i] - miny, r2 = sy[i + 1] - miny;
        vector<int> xs;
        for (int j = 0; j < V; j++) {
            auto p1 = p[j], p2 = p[(j + 1) % V];
            if (p1.first == p2.first && min(p1.second, p2.second) <= r1 && max(p1.second, p2.second) >= r2)
                xs.push_back(p1.first);
        }
        sort(xs.begin(), xs.end());
        for (int j = 0; j < (int)xs.size(); j += 2)
            rs.push_back({xs[j], r1, xs[j + 1], r2});
    }
    
    long long tot = 0;
    for (auto &r : rs) tot += (long long)(r.xb - r.xa) * (r.yb - r.ya);
    
    // 统计答案
    int ans = 0;
    for (int i = 1; i <= R - H + 1; i++) {
        for (int j = 1; j <= C - W + 1; j++) {
            // 注意坐标偏移：g 为 0 索引，i, j 为前缀和 1 索引
            int c = g[i + rs[0].ya - 1][j + rs[0].xa - 1] - 'a';
            long long cur = 0;
            for (auto &r : rs)
                cur += query(c, i + r.ya, j + r.xa, i + r.yb - 1, j + r.xb - 1);
            if (cur == tot) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

进阶补充：格点积分法

形式化的介绍：格点积分法的核心思想是 “化面为线”。其将二维区域（面）的统计问题，转化为对其边界（线）的代数和计算。对于正交多边形（边平行于坐标轴），我们可以通过绕行边界一周，累加每条边对应的“投影贡献”来得到内部信息。

看上去很深奥，但其实它的原理和我们初中几何里的铅锤高法求面积很像。铅锤高法是把斜着的三角形投影到了垂直方向（铅锤）和水平方向上，利用 $\Delta x$ 和 $\Delta y$ 来间接算面积。格点积分则是把这种思想推广到了任意多边形。

想象在坐标系中，每一条垂直边向 $y$ 轴投射出一个“影子矩形”。我们规定：

• 向上运动的边：投射出的影子面积为正。
• 向下运动的边：投射出的影子面积为负。

当多边形闭合时，多边形外部的“影子”会被一正一负两次扫描完全抵消，而多边形内部的区域只被单向扫描过一次。因此，最终所有边投影面积的累加和，其绝对值恰好等于多边形的总面积。