2 solutions

  • 1
    @ 2025-1-13 10:41:42
    /*
    by kivi for 2025 WC 2024.12.18
    */
    //打砖块
    //有一个 n*m 的二元网格 grid ,其中 1 表示砖块,0 表示空白砖块
    //稳定(不会掉落)的前提是:
    //一块砖直接连接到网格的顶部,或者至少有一块相邻(4 个方向之一)砖块稳定 不会掉落
    //给你k次操作 进行hits ,这是需要依次消除砖块的位置
    //每当消除 hits[i]=(rowi,coli)位置上的砖块时,对应位置的砖块(若存在)会消失
    //然后其他的砖块可能因为这一消除操作而 掉落一旦砖块掉落,它会立即从网格 grid 中消失
    //(即,它不会落在其他稳定的砖块上)
    //输出k个数字 ,其中 k[i] 表示第 i 次消除操作对应掉落的砖块数目。
    //注意,消除可能指向是没有砖块的空白位置,如果发生这种情况,则没有砖块掉落。
    
    #include <bits/stdc++.h>
    using namespace std;
    const int N = 205;
    int grid[N][N];
    int n, m, k;
    int ans[N * N];
    vector<pair<int, int>>hit;
    
    int dfs(int x, int y) {
    	//如果越界或者不为1,说明没有砖块掉落,答案为0
    	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);
    }
    
    //判断是否开始洪水填充,首先必须为1,其次上下左右必须有2或者自己就是在天花板上
    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;
    	for (int i = 1; i <= n; i++)
    		for (int j = 1; j <= m; j++)
    			cin >> grid[i][j];
    	cin >> k;
    	//读入炮弹信息,并把炮弹位置-1做预处理
    	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]++;//首先炮弹位置+1
    		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;
    }
    
    /*
    6 7
    1 1 1 1 0 1 0
    0 1 1 0 0 1 1
    0 1 1 1 0 1 1
    0 0 0 1 0 0 0
    0 0 0 1 1 0 0
    0 0 0 0 0 0 0
    5
    4 4
    1 6
    2 2
    2 3
    4 5
    
    
    2 4 0 3 0
    */
    
    
    
    • 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;
      }
      
      • 1

      Information

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