2 solutions
-
1
/* 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 */
Information
- ID
- 4897
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 5
- Tags
- # Submissions
- 138
- Accepted
- 0
- Uploaded By