【日常水题-bfs】求细胞数量-白红宇

【日常水题-bfs】求细胞数量

阅读量：5236 次

发布时间：2019-06-14

本文共 1270 字，大约阅读时间需要 4 分钟。

一题让我学会bfs系列qaq

1 #include
     
       2 #include
      
        3 using namespace std; 4 const int sz = 110; 5 int n, m, ans = 0; 6 int dx[4]={
   0,1,0,-1}; 7 int dy[4]={
   1,0,-1,0}; 8 int plat[sz][sz]; 9 int q[sz][3];10 struct node {11     int x, y;12 };13 void bfs(int x,int y) {14     int head = 1, tail = 1, mx, my;15     plat[x][y] = 0;16     q[1][1] = x, q[1][2] = y;17     while(head<=tail) {18         for(int i = 0; i < 4; i++) {19             mx = q[head][1] + dx[i];20             my = q[head][2] + dy[i];21             if(mx>=1&&my>=1&&mx<=n&&my<=m&&plat[mx][my]) {22                 tail++;23                 q[tail][1] = mx;24                 q[tail][2] = my;25                 plat[mx][my] = 0;26             }27         }28         head++;29     }30 }31 int main() {32     scanf("%d%d",&n,&m);33     for(int i = 1; i <= n; i++) {34         for(int j = 1; j <= m; j++) 35             scanf("%1d",&plat[i][j]);36     }37     for(int i = 1; i <= n; i++) {38         for(int j = 1; j <= m; j++) {39             if(plat[i][j]) {40                 bfs(i,j);41                 ans++;42             }43         }44     }45     printf("%d",ans);46     return 0;47 }