結果

問題 No.157 2つの空洞
ユーザー @abcde@abcde
提出日時 2019-04-21 12:10:16
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 7,372 bytes
コンパイル時間 1,627 ms
コンパイル使用メモリ 166,016 KB
実行使用メモリ 6,816 KB
最終ジャッジ日時 2024-10-05 08:12:31
合計ジャッジ時間 2,153 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 1 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 1 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 1 ms
5,248 KB
testcase_13 AC 1 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 2 ms
6,816 KB
testcase_19 AC 2 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// yukicoder(No.697 池の数はいくつか)
// https://yukicoder.me/submissions/329835
// -> 上記を拡張してみた.
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
constexpr int MAX = 625;
constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int H, W;
char board[MAX];
int memo[MAX];
// distance を 変数名で使用すると, In file included from /usr/include/c++/4.8.2/bits/stl_algobase.h:66:0 ...
// のような error となるので, 使わない.
// int dist[MAX];

// 幅優先探索.
// https://ja.wikipedia.org/wiki/幅優先探索
// 迷路を幅優先探索する.
// ※bfsの動作確認用.
// @param c: 探索地点の迷路の座標.
// @param d: 池の番号.
// @return: 特に無し.
void bfs(int c, int d){
    
    // 1. 終了条件設定.
    if(board[c] == '#') 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] == '.' && memo[n] == 0) memo[n] = d, q.push(n);
        }
    }
    return;
}

// 幅優先探索.
// https://ja.wikipedia.org/wiki/幅優先探索
// 迷路を幅優先探索する.
// ※bfsの動作確認用.
// @param c: 探索地点の迷路の座標.
// @param s: スタート地点.
// @param g: ゴール地点.
// @param dist: 探索距離を保存する二次元配列.
// @param sIndex: 探索距離を保存する二次元配列のインデックス.
// @return: 特に無し.
void getDistance(int c, int s, int g, int dist[][MAX], int sIndex){
    
    // 1. 終了条件設定.
    if(dist[sIndex][c] >= 1) return;
    
    // 2. 空のキュー.
    queue<int> q;
    
    // 3. 訪問済みフラグ設定.
    dist[sIndex][c] = 0;
    
    // 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] == s || memo[n] == g) continue;
            // 8. 訪問可能 かつ 未訪問 のマス であれば, 最短距離を設定.
            if(memo[n] != s && memo[n] != g && dist[sIndex][n] == 0) dist[sIndex][n] = dist[sIndex][v] + 1, q.push(n);
        }
    }
    return;
}

int main() {
    
    // 1. 入力情報取得.
    cin >> W >> H;
    FOR(i, 0, H){
        string s;
        cin >> s;
        FOR(j, 0, W) board[i * W + j] = s[j];
    }
    
    // 2. 空洞の分割.
    int counter = 1;
    FOR(i, 0, H * W){
        if(board[i] == '.' && memo[i] == 0){
            bfs(i, counter);
            counter++;
        }
    }
    // ex.
    // [入力例]
    // #########
    // #.####.##
    // #..###.##
    // #..###..#
    // #########
    // ↓
    // [memo]
    // 0 0 0 0 0 0 0 0 0 
    // 0 1 0 0 0 0 2 0 0 
    // 0 1 1 0 0 0 2 0 0 
    // 0 1 1 0 0 0 2 2 0 
    // 0 0 0 0 0 0 0 0 0 
    // FOR(i, 0, H){
    //     FOR(j, 0, W){
    //         cout << memo[i * W + j] << " ";
    //     }
    //     cout << endl;
    // }
    
    // 3. スタート地点の個数をカウント.
    int sCount = 0;
    FOR(i, 0, H * W) if(memo[i] == 1) sCount++;
    
    // 4. 空洞から別の空洞へ探索してみる.
    // ※スタート地点の個数分実施？？？
    int dist[sCount][MAX];
    FOR(i, 0, sCount) FOR(j, 0, MAX) dist[i][j] = 0;
    int startIndex = 0;
    FOR(i, 0, H * W){
        if(memo[i] == 1){
            getDistance(i, 1, 2, dist, startIndex);
            startIndex++;
        }
    }
    
    // ex.
    // [入力例]
    // #########
    // #.####.##
    // #..###.##
    // #..###..#
    // #########
    // ↓
    // [dist]
    // index=0
    // 2 1 2 3 4 5 6 7 8 
    // 1 0 1 2 3 4 0 8 9 
    // 2 0 0 3 4 5 0 9 10 
    // 3 0 0 4 5 6 0 0 11 
    // 4 5 6 5 6 7 8 9 10 
    // index=1
    // 3 4 5 6 7 8 9 10 11 
    // 2 0 6 7 8 9 0 11 12 
    // 1 0 0 8 9 10 0 12 13 
    // 2 0 0 7 8 9 0 0 12 
    // 3 4 5 6 7 8 9 10 11 
    // index=2
    // 4 3 2 3 4 5 6 7 8 
    // 5 0 1 2 3 4 0 8 9 
    // 6 0 0 1 2 3 0 9 10 
    // 7 0 0 2 3 4 0 0 9 
    // 6 5 4 3 4 5 6 7 8 
    // index=3
    // 4 5 6 7 8 9 10 11 12 
    // 3 0 7 6 7 8 0 12 11 
    // 2 0 0 5 6 7 0 11 10 
    // 1 0 0 4 5 6 0 0 9 
    // 2 1 2 3 4 5 6 7 8 
    // index=4
    // 7 6 5 4 5 6 7 8 9 
    // 6 0 4 3 4 5 0 9 10 
    // 5 0 0 2 3 4 0 10 9 
    // 4 0 0 1 2 3 0 0 8 
    // 3 2 1 2 3 4 5 6 7 
    // FOR(m, 0, sCount){
    //     cout << "index=" << m << endl;
    //     FOR(i, 0, H){
    //         FOR(j, 0, W){
    //             cout << dist[m][i * W + j] << " ";
    //         }
    //         cout << endl;
    //     }
    // }
    
    // 4. 最短距離を探索.
    // memo[i] == 2 となる各地点の上下左右(index を j と見て)について, 
    // memo[j] != 2 であることを確認しながら, dist[index][j] の最小値を確認し, 更新していく.
    int ans = 1e8;
    FOR(i, 0, H){
        FOR(j, 0, W){
            // memo[i] == 2 (ゴール地点) を 設定.
            if(memo[i * W + j] == 2){
                // 上下左右を確認.
                int nx, ny, n;
                FOR(k, 0, 4){
                    nx = j + dx[k];
                    ny = i + dy[k];
                    n = nx + ny * W;
                    // 訪問不可能なマス であれば, 処理をスキップ.
                    if(n < 0 || nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
                    // memo[n] != 2 (ゴール手前の地点) を 設定し, dist[index][n] の 最小値 を 確認.
                    if(memo[n] != 2){
                        // ※ 最小値 は, 1以上 のはずなので, dist[l][n] > 0 に限定して, 最小値を更新.
                        FOR(l, 0, sCount) if(dist[l][n] > 0) ans = min(ans, dist[l][n]);
                    }
                }
            }
        
        }
    }
    
    // 5. 出力 ～ 後処理.
    cout << ans << endl;
    return 0;
    
}
0