洛谷 UVA572. 油田(求连通块)
原题链接
简单
作者:
Aqiw
,
2025-04-16 14:36:24
· 河北
,
所有人可见
,
阅读 1
油田
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 120;
char g[N][N];
int st[N][N], idx;
int n, m;
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {1, 0, 1, -1, 1, -1, 0, 1};
void dfs(int a, int b) {
if (a < 0 || b < 0 || a >= n || b >= m || g[a][b] != '@' || st[a][b]) return;
st[a][b] = idx;
for (int i = 0; i < 8; i++) {
int x = dx[i] + a, y = dy[i] + b;
dfs(x, y);
}
}
int main() {
while (1) {
cin >> n >> m;
if (n == 0 && m == 0) return 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> g[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
st[i][j] = 0;
}
}
idx = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == '@' &&!st[i][j]) {
idx++;
dfs(i, j);
}
}
}
cout << idx << endl;
}
return 0;
}