// コメント修正して, 再提出. #include using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) constexpr int MAX = 9e6; // constexpr int MAX = 64; constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; int H, W; int board[MAX]; int memo[MAX]; // 幅優先探索. // https://ja.wikipedia.org/wiki/幅優先探索 // 迷路を幅優先探索する. // ※bfsの動作確認用. // @param c: 探索地点の迷路の座標. // @param l: 池の番号(※1以上). // @param: 特に無し. void bfs(int c, int l){ // 1. 終了条件設定. if(memo[c] >= 1) return; if(board[c] == 0) return; // 2. 空のキュー. queue q; // 3. 訪問済みフラグ設定. memo[c] = l; // 4. 探索地点 c をキュー q に追加. q.push(c); while(!q.empty()){ // 5. キューから取り出す. int v = q.front(); q.pop(); // 6. 取り出した要素を処理. // x: 列方向, y: 行方向 で考える. int nx, ny, n; int cx = v % W , cy = v / W; FOR(i, 0, 4){ nx = cx + dx[i]; ny = cy + dy[i]; n = nx + ny * W; // cout << "cx=" << cx << " nx=" << nx << " cy=" << cy << " ny=" << ny << " n=" << n << " c=" << c << endl; // 7. 訪問不可能なマス であれば, 処理をスキップ. if(n < 0 || nx < 0 || nx >= W || ny < 0 || ny >= H) continue; if(memo[n] == l) continue; // 8. 水のマスで, 訪問可能 かつ 未訪問 であれば, 訪問済みを設定. if(board[n] == 1 && memo[n] == 0) memo[n] = l, q.push(n); } } return; } int main() { // 1. 入力情報取得. cin >> H >> W; FOR(i, 0, H * W) cin >> board[i]; // 2. 探索開始の頂点(根)を指定(頂点0番)し, 各頂点までの最短距離を保存. int counter = 1; FOR(i, 0, H * W) if(board[i] == 1) bfs(i, counter), counter++; // 3. 出力. // ex. // 10 12 // 1 0 1 0 0 0 1 0 1 0 1 1 // 1 1 1 0 0 0 1 0 0 1 0 1 // 1 0 1 0 1 0 1 1 1 0 1 0 // 1 0 1 0 0 0 1 1 1 0 0 1 // 1 0 1 0 0 0 1 0 1 1 1 0 // 1 0 1 0 0 1 1 1 1 1 1 0 // 1 0 1 0 0 0 1 1 1 0 0 0 // 1 0 1 0 0 1 1 0 1 1 1 0 // 1 0 1 0 0 0 1 1 1 0 1 0 // 1 0 1 0 0 0 1 1 0 1 0 1 // // 1 0 1 0 0 0 3 0 4 0 5 5 // 1 1 1 0 0 0 3 0 0 11 0 5 // 1 0 1 0 15 0 3 3 3 0 19 0 // 1 0 1 0 0 0 3 3 3 0 0 25 // 1 0 1 0 0 0 3 0 3 3 3 0 // 1 0 1 0 0 3 3 3 3 3 3 0 // 1 0 1 0 0 0 3 3 3 0 0 0 // 1 0 1 0 0 3 3 0 3 3 3 0 // 1 0 1 0 0 0 3 3 3 0 3 0 // 1 0 1 0 0 0 3 3 0 62 0 63 // -> 10個 で良さそう. // FOR(i, 0, H * W) cout << memo[i] << " "; // cout << endl; map ans; FOR(i, 0, H * W) if(memo[i] > 0) ans[memo[i]]++; cout << ans.size() << endl; return 0; }