题目1335【例2-4】连通块题目描述一个n × m的方格图一些格子被涂成了黑色在方格图中被标为1白色格子标为0。问有多少个四连通的黑色格子连通块。四连通的黑色格子连通块指的是一片由黑色格子组成的区域其中的每个黑色格子能通过四连通的走法上下左右只走黑色格子到达该联通块中的其它黑色格子。输入第一行两个整数n,m(1≤n,m≤100)表示一个n × m的方格图。接下来n行每行m个整数分别为0或1表示这个格子是黑色还是白色。输出一行一个整数ans表示图中有ans个黑色格子连通块。时空限制1s / 64MB样例输入3 3 1 1 1 0 1 0 1 0 1样例输出3代码#includebits/stdc.husingnamespacestd;typedefpairint,intPII;constintN10010;intn,m,g[N][N],ans;intdx[10]{-1,1,0,0},dy[10]{0,0,-1,1};voidbfs(intx,inty){queuePIIq;q.push({x,y});g[x][y]0;while(!q.empty()){PII tq.front();q.pop();for(inti0;i4;i){intxxt.firstdx[i],yyt.seconddy[i];if(xx0xxnyy0yymg[xx][yy]){q.push({xx,yy});g[xx][yy]0;}}}}intmain(){cinnm;for(inti0;in;i)for(intj0;jm;j)cing[i][j];for(inti0;in;i)for(intj0;jm;j){if(g[i][j]){bfs(i,j);ans;}}coutans;return0;}结果 【题解-信息学奥赛一本通】1335：【例2-4】连通块
题目1335【例2-4】连通块题目描述一个n × m的方格图一些格子被涂成了黑色在方格图中被标为1白色格子标为0。问有多少个四连通的黑色格子连通块。四连通的黑色格子连通块指的是一片由黑色格子组成的区域其中的每个黑色格子能通过四连通的走法上下左右只走黑色格子到达该联通块中的其它黑色格子。输入第一行两个整数n,m(1≤n,m≤100)表示一个n × m的方格图。接下来n行每行m个整数分别为0或1表示这个格子是黑色还是白色。输出一行一个整数ans表示图中有ans个黑色格子连通块。时空限制1s / 64MB样例输入3 3 1 1 1 0 1 0 1 0 1样例输出3代码#includebits/stdc.husingnamespacestd;typedefpairint,intPII;constintN10010;intn,m,g[N][N],ans;intdx[10]{-1,1,0,0},dy[10]{0,0,-1,1};voidbfs(intx,inty){queuePIIq;q.push({x,y});g[x][y]0;while(!q.empty()){PII tq.front();q.pop();for(inti0;i4;i){intxxt.firstdx[i],yyt.seconddy[i];if(xx0xxnyy0yymg[xx][yy]){q.push({xx,yy});g[xx][yy]0;}}}}intmain(){cinnm;for(inti0;in;i)for(intj0;jm;j)cing[i][j];for(inti0;in;i)for(intj0;jm;j){if(g[i][j]){bfs(i,j);ans;}}coutans;return0;}结果 RELATED READING
延伸阅读
更多一线实战笔记与深度复盘，助您持续精进
)
