题意:给定一个n*m的网格块,如果一个块水平或垂直方向没有相邻支撑就会掉下去

有q次询问,每次会掉下去一块,问连锁反应新掉下的块数

n,m<=2e3,q<=1e5

思路:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 typedef unsigned int uint;
 5 typedef unsigned long long ull;
 6 typedef pair<int,int> PII;
 7 typedef pair<ll,ll> Pll;
 8 typedef vector<int> VI;
 9 typedef vector<PII> VII;
10 #define N  2100
11 #define M  4100000
12 #define fi first
13 #define se second
14 #define MP make_pair
15 #define pi acos(-1)
16 #define mem(a,b) memset(a,b,sizeof(a))
17 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
18 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
19 #define lowbit(x) x&(-x)
20 #define Rand (rand()*(1<<16)+rand())
21 #define id(x) ((x)<=B?(x):m-n/(x)+1)
22 #define ls p<<1
23 #define rs p<<1|1
24
25 const ll MOD=1e9+7,inv2=(MOD+1)/2;
26       double eps=1e-6;
27       int INF=1e9;
28       int dx[4]={-1,1,0,0};
29       int dy[4]={0,0,-1,1};
30
31 int b[N][N],n,m,s;
32
33 int read()
34 {
35    int v=0,f=1;
36    char c=getchar();
37    while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
38    while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
39    return v*f;
40 }
41
42 int isok(int x,int y)
43 {
44     if(x>=1&&x<=n&&y>=1&&y<=m) return 1;
45     return 0;
46 }
47
48 int drop(int x,int y)
49 {
50     int s1=0,s2=0;
51     if(isok(x-1,y)&&b[x-1][y]==1) s1++;
52     if(isok(x+1,y)&&b[x+1][y]==1) s1++;
53     if(isok(x,y-1)&&b[x][y-1]==1) s2++;
54     if(isok(x,y+1)&&b[x][y+1]==1) s2++;
55     if(s1>0&&s2>0) return 1;
56     return 0;
57 }
58
59 void dfs(int x,int y)
60 {
61     b[x][y]=1;
62     s++;
63     rep(i,0,3)
64     {
65         int tx=x+dx[i],ty=y+dy[i];
66         if(isok(tx,ty)&&b[tx][ty]==0&&drop(tx,ty)) dfs(tx,ty);
67     }
68 }
69
70
71 int main()
72 {
73     //freopen("1.in","r",stdin);
74     //freopen("1.out","w",stdout);
75
76     int cas;
77     scanf("%d",&cas);
78
79     while(cas--)
80     {
81         n=read(),m=read();
82         int q=read();
83         rep(i,1,n)
84          rep(j,1,m) b[i][j]=0;
85         rep(i,1,q)
86         {
87             int x=read(),y=read();
88             s=0;
89             if(b[x][y]==0) dfs(x,y);
90             printf("%d\n",s);
91         }
92     }
93
94     return 0;
95 }
01-25 23:26