题意:
就是给你一个n行m列的矩形,后面将会有q次操作,每次操作会输入x,y表示要击碎第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 shudui
12 {
13 int x,y;
14 } str1,str2;
15 int p[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
16 int n,m,w[maxn][maxn],xx[maxn],yy[maxn];
17 queue
18 bool panduan(int y,int x)
19 {
20 int flag=0;
21 if(yy[y])
22 {
23 if(xx[x])
24 return 0;
25 else return 1;
26 }
27 else return 1;
28 }
29 int bfs(int ans)
30 {
31 while(!r.empty())
32 {
33 str1=r.front();
34 r.pop();
35 for(int i=0; i<4; ++i)
36 {
37 int x=str2.x=str1.x+p[i][0];
38 int y=str2.y=str1.y+p[i][1];
39 if(x<1 || y<1 || x>m || y>n || w[y][x])
40 {
41 continue;
42 }
43 if((w[y-1][x] || w[y+1][x]) && (w[y][x+1] || w[y][x-1]))
44 {
45 ans++;
46 w[y][x]=1;
47 r.push(str2);
48 }
49 }
50 }
51 return ans;
52 }
53 int v[maxn];
54 int main()
55 {
56 int t;
57 scanf("%d",&t);
58 while(t--)
59 {
60 int q;
61 memset(yy,0,sizeof(yy));
62 memset(xx,0,sizeof(xx));
63 memset(w,0,sizeof(w));
64 while(!r.empty()) r.pop();
65 scanf("%d%d%d",&n,&m,&q);
66 for(int j=1; j<=q; ++j)
67 {
68 int x,y;
69 scanf("%d%d",&y,&x);
70 int ans=0;
71 if(!w[y][x])
72 {
73 str2.x=x;
74 str2.y=y;
75 r.push(str2);
76 w[y][x]=1;
77 ans=bfs(1);
78 }
79 printf("%d\n",ans);
80 }
81 }
82 return 0;
83 }
手机扫一扫
移动阅读更方便
你可能感兴趣的文章