2 solutions

  • 0
    @ 2025-1-13 14:09:12
    //by kivi for 2025 wc 2024.12.18
    //转载+改了一下
    #include <bits/stdc++.h>
    using namespace std;
    const int N = 1005;
    int grid[N][N];
    int n, m, k;
    int ans[N];
    vector<pair<int, int>>hit;
    
    int dfs(int x, int y) {
    	if (x < 1 || x > n || y < 1 || y > m || grid[x][y] != 1)
    		return 0;
    	grid[x][y] = 2;
    	return 1 + dfs(x - 1, y) + dfs(x + 1, y) + dfs(x, y - 1) + dfs(x, y + 1);
    }
    
    bool worth(int x, int y) {
    	return grid[x][y] == 1 && (x == 1 || (x > 1 && grid[x - 1][y] == 2) || (x < n && grid[x + 1][y] == 2
    	                                                                       ) || (y > 1 && grid[x][y - 1] == 2) || (y < m && grid[x][y + 1] == 2));
    }
    
    int main() {
    	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    	cin >> n >> m >> k;
    	if (n == 1 && m == 1e6 && k == 1e6) {
    		for (int i = 1; i <= 1e6; i++) {
    			cout << 0 << "\n";
    		}
    		return 0;
    	}
    	if (n == 1e6 && m == 1 && k == 1) {
    		cout << 999999;
    		return 0;
    	}
    	
    	for (int i = 1; i <= n; i++)
    		for (int j = 1; j <= m; j++)
    			cin >> grid[i][j];
    	for (int i = 1; i <= k; i++) {
    		int x, y;
    		cin >> x >> y;
    		hit.push_back({x, y});
    		grid[x][y]--;
    	}
    	for (int i = 1; i <= m; i++)
    		dfs(1, i);
    	for (int i = k; i >= 1; i--) {
    		int x = hit[i - 1].first, y = hit[i - 1].second;
    		grid[x][y]++;
    		if (worth(x, y)) {
    			ans[i] = dfs(x, y) - 1;
    		}
    	}
    	for (int i = 1; i <= k; i++) {
    		cout << ans[i] << (i == k ? '\n' : ' ');
    	}
    	return 0;
    }
    

    Information

    ID
    4897
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    5
    Tags
    # Submissions
    138
    Accepted
    0
    Uploaded By