■感想.
1. どこかで類題を見た記憶があったので, 探したところ, yukicoder の No.697 池の数はいくつか に似ていることが分かった.
2. 上記の類題を適用するため, 埋め立て後の陸地の個数をカウントする方法で, 本問の解答方針とした.
■C++版プログラム(問題B／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) constexpr int MAX = 100; constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; int H, W; char board[MAX]; int memo[MAX]; // 幅優先探索. // https://ja.wikipedia.org/wiki/幅優先探索 // 迷路を幅優先探索する. // ※bfsの動作確認用. // @param c: 探索地点の迷路の座標. // @param d: 池の番号. // @return: 特に無し. void bfs(int c, int d){ // 1. 終了条件設定. if(board[c] == 'x') return; // 2. 空のキュー. queue<int> q; // 3. 訪問済みフラグ設定. memo[c] = d; // 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] == d) continue; // 8. 訪問可能 かつ 未訪問 のマス であれば, 訪問済みを設定. if(board[n] == 'o' && memo[n] == 0) memo[n] = d, q.push(n); } } return; } int main() { // 1. 入力情報取得. W = 10, H = 10; FOR(i, 0, H){ string s; cin >> s; FOR(j, 0, W) board[i * W + j] = s[j]; } // 2. 海を1マスだけ陸地にして, 1つの島に出来るかを確認. int counter = 0; bool ans = false; FOR(i, 0, H * W){ if(board[i] == 'x'){ // 2-1. 海を1マスだけ陸地にしてみる. board[i] = 'o'; // 2-2. 陸地の分割. // cout << "----- " << "i=" << i << " counter=" << counter <<" -----" << endl; FOR(j, 0, H * W) if(board[j] == 'o' && memo[j] == 0) counter++, bfs(j, counter); // FOR(k, 0, H){ // FOR(l, 0, W){ // cout << memo[k * W + l] << " "; // } // cout << endl; // } // cout << "----- " << "i=" << i << " counter=" << counter <<" -----" << endl; // ex. // [入力例] // xxxxoxxxxx // xxxxoxxxxx // xxxxoxxxxx // xxxxoxxxxx // ooooxooooo // xxxxoxxxxx // xxxxoxxxxx // xxxxoxxxxx // xxxxoxxxxx // xxxxoxxxxx // // [探索状況(抜粋)] // ----- i=44 counter=0 ----- // 0 0 0 0 1 0 0 0 0 0 // 0 0 0 0 1 0 0 0 0 0 // 0 0 0 0 1 0 0 0 0 0 // 0 0 0 0 1 0 0 0 0 0 // 1 1 1 1 1 1 1 1 1 1 // 0 0 0 0 1 0 0 0 0 0 // 0 0 0 0 1 0 0 0 0 0 // 0 0 0 0 1 0 0 0 0 0 // 0 0 0 0 1 0 0 0 0 0 // 0 0 0 0 1 0 0 0 0 0 // ----- i=44 counter=1 ----- // -> YES 正しく判定されているように見える. // 2-3. 1つの島に出来た場合は, 後続処理をスキップ. if(counter == 1){ ans = true; break; } // 2-4. 元に戻す. counter = 0; board[i] = 'x'; FOR(j, 0, H * W) memo[j] = 0; } } // 3. 出力 ～ 後処理. if(ans) cout << "YES" << endl; else cout << "NO" << endl; return 0; } |