模拟
利用pick公式area=on/2+in-1
计算in的时候从外围广搜所有不是in的点，再用总数减去。
View Code #include#include #include #include #include using namespace std;#define maxn 150struct Point{ int x, y;} q[maxn * maxn];char map[maxn][maxn];int n, m;bool vis[maxn][maxn];int dir[4][2] ={{ 1, 1 },{ 1, -1 },{ -1, 1 },{ -1, -1 } };int dir1[4][2] ={{ 1, 0 },{ 0, -1 },{ 0, 1 },{ -1, 0 } };void input(){ scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) scanf("%s", map[i]);}bool out_of_bound(Point &a){ return a.x < 0 || a.y < 0 || a.x > n + 2 || a.y > m + 2;}bool ok(Point &a, Point &b){ int x = min(a.x, b.x) - 1; int y = min(a.y, b.y) - 1; if (x < 0 || y < 0 || x >= n || y >= m) return true; return map[x][y] == '.';}bool empty(int x, int y, char ch){ if (x < 0 || y < 0 || x >= n || y >= m) return true; return map[x][y] != ch;}bool on_the_bound(Point &a){ return !empty(a.x - 2, a.y - 2, '\\') || !empty(a.x - 1, a.y - 1, '\\') || !empty(a.x - 1, a.y - 2, '/') || !empty(a.x - 2, a.y - 1, '/');}void work(){ memset(vis, 0, sizeof(vis)); vis[0][0] = true; int front, rear; front = rear = 0; Point a; a.x = a.y = 0; q[rear++] = a; int cnt = 1; while (front != rear) { a = q[front++]; for (int i = 0; i < 4; i++) { Point b; b.x = a.x + dir[i][0]; b.y = a.y + dir[i][1]; if (!out_of_bound(b) && !on_the_bound(b) && ok(a, b) && !vis[b.x][b.y]) { q[rear++] = b; vis[b.x][b.y] = true; cnt++; } b.x = a.x + dir1[i][0]; b.y = a.y + dir1[i][1]; if (!out_of_bound(b) && !on_the_bound(b) && !vis[b.x][b.y]) { q[rear++] = b; vis[b.x][b.y] = true; cnt++; } } } int on = n * m; for (int i = 0; i < n; i++) on -= count(map[i], map[i] + m, '.'); cnt += on; int in = (n + 3) * (m + 3) - cnt; int ans = on / 2 + in - 1; printf("%d\n", ans);}int main(){ //freopen("t.txt", "r", stdin); input(); work();}