AC

123Y456  •  1个月前


include <bits/stdc++.h>

using namespace std;

const int N = 305; int a[N][N];

bool vis[N][N] = {0}; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; int n, m;

void dfs(int x, int y) {

if (x < 0 || x > n || y < 0 || y > m || a[x][y] || vis[x][y]) {
	return;
}
vis[x][y] = 1;
for (int i = 0; i < 4; ++i) {
	int nx = x + dx[i];
	int ny = y + dy[i];
	dfs(nx, ny);
}

}

void dfs_1(int x, int y) {

if (x < 0 || x > n || y < 0 || y > m || a[x][y] == 0) {
	return;
}
a[x][y] = 0;
dfs_1(x + 1, y);
dfs_1(x - 1, y);
dfs_1(x, y + 1);
dfs_1(x, y - 1);

}

int main() {

int ans = 0;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) {
	for (int j = 0; j < m; ++j) {
		scanf("%d", &a[i][j]);
	}
}
for (int i = 0; i < n; ++i) {
	for (int j = 0; j < m; ++j) {
		if (a[i][j] == 1 && !vis[i][j]) {

// dfs(i, j);

			dfs_1(i, j);
			ans++;
		}
	}
}
printf("%d", ans);

return 0;

}


评论:

请先登录,才能进行评论