AcWing 6037. 连通块
原题链接
简单
作者:
sky-koi
,
2024-11-18 15:09:35
,
所有人可见
,
阅读 4
# include <iostream>
using namespace std;
const int N = 110;
int n, m;
int maze[N][N];
bool vis[N][N];
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool in(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < m;
}
int cnt; // 连通块的个数
void dfs(int x, int y) {
vis[x][y] = true;
for (int i = 0; i < 4; i++) {
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if (in(tx, ty) && !vis[tx][ty] && maze[tx][ty] == 1) {
dfs(tx, ty);
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> maze[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (maze[i][j] == 1 && !vis[i][j]) {
cnt++;
dfs(i, j);
}
}
}
cout << cnt << endl;
return 0;
}