hdu-6699 Block Breaker

题意：

就是给你一个n行m列的矩形，后面将会有q次操作，每次操作会输入x，y表示要击碎第x行第y列的石块，当击碎它之后还去判断一下周围石块是否牢固

如果一个石块的左右两边至少一个已经被击碎且上下也至少一个被击碎，那么这个石块就是不牢固的，可以把这个石块也击碎

对于每一对x，y；要输出一个整数表示此次操作击碎石块多少个

题解：

对于每输入的一对x，y；先判断这个点的石块还在不在了，不在就输出0，在的话标记一下，在以此处为起点开始bfs搜索，搜索过程中经过的点也要标记

再按照石块是否牢固的判断方法对搜索过程中的石块进行判断

代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 #include<vector>

 6 #include<queue>

 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<shudui>r;

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 }

巴特西

hdu-6699 Block Breaker

最新文章

热门文章