P7411 [USACO21FEB] Comfortable Cows S （搜索）

P7411 [USACO21FEB] Comfortable Cows S

搜索

容易知道任意时刻的不合法的位置，并且决策只有将空着的位置补起来。

每次加入一个点，判断其自身、上下左右是否变得不合法，往下递归即可。

复杂度分析，每个点只会不合法一次（修改后就变得合法），所以只会遍历一次，复杂度是 \(O(n^2)\)。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define mk std::make_pair
#define fi first
#define se second
#define pb push_back

using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 1510;
int n, ans;
bool vis[N][N], mp[N][N];
bool chk(int x, int y) {
	int cnt = vis[x + 1][y] + vis[x][y + 1];
	if(x - 1 >= 0) cnt += vis[x - 1][y];
	if(y - 1 >= 0) cnt += vis[x][y - 1];
	return cnt == 3;
}
void dfs(int x, int y) {
	vis[x][y] = 1;
	if(chk(x, y)) {
		ans++;
		if(!vis[x - 1][y] && x > 0) dfs(x - 1, y), mp[x - 1][y] = 1;
		if(!vis[x + 1][y]) dfs(x + 1, y), mp[x + 1][y] = 1;
		if(!vis[x][y - 1] && y > 0) dfs(x, y - 1), mp[x][y - 1] = 1;
		if(!vis[x][y + 1]) dfs(x, y + 1), mp[x][y + 1] = 1;
	}
	if(x > 0 && chk(x - 1, y) && vis[x - 1][y]) dfs(x - 1, y);
	if(chk(x + 1, y) && vis[x + 1][y]) dfs(x + 1, y);
	if(y > 0 && chk(x, y - 1) && vis[x][y - 1]) dfs(x, y - 1);
	if(chk(x, y + 1) && vis[x][y + 1]) dfs(x, y + 1);
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	std::cin >> n;

	for(int i = 1; i <= n; i++) {
		int x, y;
		std::cin >> x >> y;
		x++, y++;
		if(!vis[x][y]) dfs(x, y);
		if(mp[x][y]) ans--, mp[x][y] = 0;
		std::cout << ans << "\n";
	}

	return 0;
}