AOJ 1160 How Many Islands?
問題
How Many Islands? | Aizu Online Judge
8方向に隣接した陸地を島と定義する。 フィールドの各タイルが陸か海かの情報から、いくつ島があるか数えよ。
方針
dfsで隣接した土地に同じidを振り、idが何種類あるかを数える
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for(int i=0; i<(n); ++i) int w, h; int c[51][51]; int island[51][51]; int ans; int dx[] = {1, -1, 0, 0, 1, -1, 1, -1}; int dy[] = {0, 0, 1, -1, 1, -1, -1, 1}; void dfs(int y, int x, int id) { island[y][x] = id; rep(i, 8) { int nx = x+dx[i]; int ny = y+dy[i]; if(nx>=0 && nx<w && ny>=0 && ny<h && c[ny][nx] == 1 && island[ny][nx] != id) { dfs(ny, nx, id); } } } int main(void){ while(cin >> w >> h && w) { rep(y, h) rep(x, w) cin >> c[y][x]; ans = 0; memset(island, -1, sizeof(island)); rep(y, h) { rep(x, w) { if(c[y][x]==1 && island[y][x]==-1) { dfs(y, x, ans); ans++; } } } cout << ans << endl; } }
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1889802
反省
idの更新を忘れててバグった