【範例】Flood Fill – Labeling/Coloring the Connected Components
【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c129
【解題想法】BFS
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=101;
int m, n;
char a[maxn][maxn];
void flood(int r, int c) {
int r1, c1;
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
for (int i=0; i<8; i++) {
r1 = r + dx[i];
c1 = c + dy[i];
if (r1>=0 && r1<m && c1>=0 && c1<n && a[r1][c1]=='@') {
a[r1][c1] = '*';
flood(r1, c1);
}
}
}
int main() {
string s;
while (cin >> m >> n) {
if (m==0 && n==0) break;
memset(a, '\0', sizeof(a));
for (int i=0; i<m; i++) {
cin >> s;
for (int j=0; j<n; j++) {
a[i][j] = s[j];
}
}
int ans = 0;
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
if (a[i][j] == '@') {
ans++;
flood(i, j);
}
}
}
cout << ans << endl;
}
return 0;
}
Python code (credit: Amy Chou)
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
def flood(r, c):
for i in range(8):
nr = r + dx[i]
nc = c + dy[i]
if nr >= 0 and nr < m and nc >= 0 and nc < n and g[nr][nc] == "@":
g[nr][nc] = "*"
flood(nr, nc)
while True:
m, n = map(int, input().split())
if m == 0 and n == 0:
break
g = []
for _ in range(m):
g.append(list(input()))
ans = 0
for i in range(m):
for j in range(n):
if g[i][j] == "@":
ans += 1
flood(i, j)
print(ans)