結果

問題 No.157 2つの空洞
ユーザー she11codeshe11code
提出日時 2015-05-06 22:18:58
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,026 bytes
コンパイル時間 1,261 ms
コンパイル使用メモリ 163,184 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 19:20:19
合計ジャッジ時間 1,948 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

#define LOG(...) fprintf(stderr,__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

struct P {
    int x, y, step;
};

const int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};

int w, h;
char cave[20][20];

void dfs_fill(int x, int y, int c) {
    cave[y][x] = c;
    REP(i, 4) {
        int sx = x + dx[i];
        int sy = y + dy[i];
        if (0 <= sx && sx < w && 0 <= sy && sy < h) {
            if (cave[sy][sx] == '.') {
                dfs_fill(sx, sy, c);
            }
        }
    }
}

int main() {
    cin >> w >> h;

    fill_n((char *)cave, 20*20, '#');
    REP(y, h) REP(x, w) cin >> cave[y][x];

    char c = 'A';
    REP(y, h) {
        REP(x, w) {
            if (cave[y][x] == '.') {
                dfs_fill(x, y, c);
                c = 'B';
            }
        }
    }

    queue<P> que;
    REP(y, h) {
        REP(x, w) {
            if (cave[y][x] == 'A') {
                que.push({x, y, 0});
            }
        }
    }
    while (!que.empty()) {
        P p = que.front(); que.pop();
        REP(i, 4) {
            int sx = p.x + dx[i];
            int sy = p.y + dy[i];
            if (0 <= sx && sx < w && 0 <= sy && sy < h) {
                if (cave[sy][sx] == '#') {
                    cave[sy][sx] = 'A';
                    que.push({sx, sy, p.step+1});
                } else if (cave[sy][sx] == 'B') {
                    cout << p.step << endl;
                    return 0;
                }
            }
        }
    }
}
0