每次从敲掉的位置开始bfs就行了，因为敲掉一个方块，只会直接影响其周边的方块，一层层bfs就能找出所有的跌落方块。
1 #include <cstdio> 2 #include <queue> 3 using namespace std; 4 queue <int> que[2]; 5 int n,m,q,T; 6 int mx[] = {-1,1,0,0},my[] = {0,0,-1,1}; 7 bool hav[2050][2050]; 8 bool drp(int nx,int ny) 9 { 10 if (hav[nx][ny] == false) 11 return false; 12 if (nx > n || nx < 1 || ny > m || ny < 1) 13 return false; 14 if ((hav[nx - 1][ny] && hav[nx + 1][ny]) || (hav[nx][ny - 1] && hav[nx][ny + 1])) 15 return false; 16 return true; 17 } 18 int bfs(int sx,int sy) 19 { 20 if (hav[sx][sy] == false) 21 return 0; 22 int res = 1; 23 que[0].push(sx); 24 que[1].push(sy); 25 hav[sx][sy] = false; 26 while (que[0].empty() == false) 27 { 28 int tx = que[0].front(); 29 int ty = que[1].front(); 30 que[0].pop(); 31 que[1].pop(); 32 for (int i = 0;i <= 3;i++) 33 { 34 int nx = tx + mx[i]; 35 int ny = ty + my[i]; 36 if (drp(nx,ny) == true) 37 { 38 hav[nx][ny] = false; 39 res++; 40 que[0].push(nx); 41 que[1].push(ny); 42 } 43 } 44 } 45 return res; 46 } 47 int main() 48 { 49 for (scanf("%d",&T); T != 0; T--) 50 { 51 scanf("%d%d%d",&n,&m,&q); 52 for (int i = 0;i <= n + 1;i++) 53 for (int j = 0;j <= m + 1;j++) 54 hav[i][j] = true; 55 int tx,ty; 56 for (int i = 1; i <= q; i++) 57 { 58 scanf("%d%d",&tx,&ty); 59 printf("%d ",bfs(tx,ty)); 60 } 61 } 62 return 0; 63 }