The Number of Island
教科書的なDFSの問題なんだが、入力ケースの終わりがちょっと特殊だった。 Patisserie | Aizu Online Judgeを彷彿とさせる。。
bool visited[13][13]; string mp[13]; int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; void solve(int x, int y) { visited[x][y]=1; for (int i =0; i < 4;i++) { int nx=x+dx[i], ny=y+dy[i]; if (0<=nx&&nx<12&&0<=ny&&ny<12) { if (!visited[nx][ny]){ solve(nx, ny); } } } } int main() { while (1) { string s; for (int i=0;i<4;i++){ getline(cin, s); if (s!="")break; } if (s=="")break; mp[0]=s; for(int i = 0; i < 11; i++) cin >> mp[i+1]; memset(visited, 0, sizeof(visited)); for (int i = 0; i < 12; i++) { for (int j = 0; j < 12; j++) { if (mp[i][j]=='0') { visited[i][j]=1; } } } int res=0; for(int i=0;i<12;i++) { for(int j=0;j<12;j++) { if (visited[i][j])continue; if (mp[i][j]=='1'){ solve(i, j); res++; } } } cout << res << endl; } return 0; }