HDU6699石块破碎者

题目描述：

给定一个n行m列的矩阵，其中每个单元格代表一块石块。接下来进行q次操作，每次操作提供一个坐标(x, y)，表示要击碎位于第x行第y列的石块。在击碎指定石块后，还需要检查其周围的石块是否因为缺少支撑而变得不稳定。具体来说，如果一个石块的左右或上下至少有一个方向上的相邻石块已被击碎，则认为该石块是不稳定的，并应随之击碎。对于每次操作，需要输出由于此次操作直接或间接导致的石块击碎总数。

解决方案：

对于每次输入的坐标(x, y)，首先检查该位置的石块是否存在。如果不存在，则输出0；如果存在，则对其进行标记，并以该位置为起点执行广度优先搜索(BFS)。在搜索过程中，对每个访问到的节点进行标记，并根据石块稳定性的定义检查这些石块是否应该被击碎。此过程会递归地检查和击碎所有因初始击碎操作而变得不稳定的石块。

实现代码：

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 #include
 7 using namespace std;
 8 const int INF=0x3f3f3f3f;
 9 const int maxn=2505;
10 typedef long long ll;
11 struct Position {
12     int x, y;
13 };
14 int direction[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
15 int n, m, grid[maxn][maxn], visited[maxn][maxn];
16 queue q;
17 bool isUnstable(int x, int y) {
18     // Check if the block at (x, y) has lost stability
19     if ((visited[x-1][y] || visited[x+1][y]) && (visited[x][y-1] || visited[x][y+1])) return true;
20     return false;
21 }
22 int BFS(int startX, int startY) {
23     int count = 1;
24     q.push({startX, startY});
25     visited[startY][startX] = 1;
26     while (!q.empty()) {
27         Position current = q.front();
28         q.pop();
29         for (int i = 0; i <4; ++i) {
30             int newX = current.x + direction[i][0];
31             int newY = current.y + direction[i][1];
32             if (newX <1 || newY <1 || newX > m || newY > n || visited[newY][newX]) continue;
33             if (isUnstable(newX, newY)) {
34                 count++;
35                 visited[newY][newX] = 1;
36                 q.push({newX, newY});
37             }
38         }
39     }
40     return count;
41 }
42 int main() {
43     int cases;
44     cin >> cases;
45     while (cases--) {
46         int queries;
47         memset(visited, 0, sizeof(visited));
48         cin >> n >> m >> queries;
49         while (!q.empty()) q.pop();
50         for (int i = 0; i 51             int x, y;
52             cin >> y >> x;
53             if (!visited[y][x]) {
54                 cout <55             } else {
56                 cout <<0 <57             }
58         }
59     }
60     return 0;
61 }

代码解释：

上述代码首先定义了一些必要的变量和结构体，包括用于表示位置的结构体Position，以及用于存储地图状态的二维数组grid和visited。通过BFS算法来实现从指定位置开始搜索并击碎所有不稳定的石块。isUnstable函数用于判断一个石块是否变得不稳定，而BFS函数则负责执行广度优先搜索，并返回此次操作中击碎的石块总数。