2019 HDOJ Multi-University Training Contest Stage 10(杭电多

 1 /* Codeforces Contest 2019_mutc_10
 2  * Problem I
 3  * Au: SJoshua
 4  */
 5 #include <queue>
 6 #include <cstdio>
 7 #include <vector>
 8 #include <string>
 9 #include <iostream>
10 
11 using namespace std;
12 
13 bool board[2002][2002];
14 int n,m,q;
15 
16 const int movement[4][2] = {
17     {0,1},{0,-1},{1,0},{-1,0}
18 };
19 
20 struct pos {
21     int x,y;
22 };
23 
24 int solve(int x,int y) {
25     int ans = 0;
26     if (board[x][y]) {
27         queue <pos> q;
28         q.push({x,y});
29         while (!q.empty()) {
30             auto t = q.front();
31             q.pop();
32             if (!board[t.x][t.y]) {
33                 continue;
34             }
35             ans++;
36             board[t.x][t.y] = 0;
37             for (int i = 0; i < 4; i++) {
38                 int nx = t.x + movement[i][0],ny = t.y + movement[i][1];
39                 if (1 <= nx && nx <= n && 1 <= ny && ny <= m && board[nx][ny]) {
40                     if ((!board[nx + 1][ny] || !board[nx - 1][ny]) && (!board[nx][ny - 1] || !board[nx][ny + 1])) {
41                         q.push({nx,ny});
42                     }
43                 }
44             }
45         }
46     }
47     return ans;
48 }
49 
50 int main(void) {
51     int T;
52     scanf("%d",&T);
53     while (T--) {
54         scanf("%d %d %d",&n,&m,&q);
55         for (int i = 0; i <= n + 1; i++) {
56             for (int j = 0; j <= m + 1; j++) {
57                 board[i][j] = true;
58             }
59         }
60         while (q--) {
61             int x,y;
62             scanf("%d %d",&x,&y);
63             printf("%dn",solve(x,y));
64         }
65     }
66     return 0;
67 }