算法
(几何) $O(4HW)$
注意到,没有自交的多边形的边数等于它的顶点数,所以我们只需统计它有多少个顶点即可。
我们可以用 $2 \times 2$ 的正方形来搜,如果其中恰有 $1$ 个或 $3$ 个黑色方块(只有相交的两条边可以构成一个顶点),则可以确定一个顶点。
比如以下这个多边形,有 $8$ 个顶点,$8$ 条边
关于自交的情况:
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::string;
int main() {
int h, w;
cin >> h >> w;
vector<string> s(h);
rep(i, h) cin >> s[i];
int ans = 0;
rep(i, h - 1)rep(j, w - 1) {
int cnt = 0;
rep(di, 2)rep(dj, 2) if (s[i + di][j + dj] == '#') cnt++;
if (cnt == 1 or cnt == 3) ++ans;
}
cout << ans << '\n';
return 0;
}