結果

問題 No.157 2つの空洞
コンテスト
ユーザー h_noson
提出日時 2016-02-19 01:03:45
言語 C++11(old_compat)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -include bits/stdc++.h -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 1,920 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,269 ms
コンパイル使用メモリ 184,952 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-03-08 16:05:33
合計ジャッジ時間 1,777 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:72:13: warning: ‘ans’ may be used uninitialized [-Wmaybe-uninitialized]
   72 |     cout << ans << endl;
      |             ^~~
main.cpp:52:9: note: ‘ans’ was declared here
   52 |     int ans;
      |         ^~~

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

#define RREP(i,s,e) for (int i = e-1; i >= s; i--)
#define rrep(i,n) RREP(i,0,n)
#define REP(i,s,e) for (int i = s; i < e; i++)
#define rep(i,n) REP(i,0,n)

#define INF 1e8

int main() {
    int w, h;
    cin >> w >> h;
    vector<string> m;
    int square[h][w];
    m.resize(h);
    rep (i,h) {
        cin >> m[i];
        fill(square[i],square[i]+w,INF);
    }

    queue<tuple<int,int,int>> next;
    bool found = false;
    rep (i,h) rep (j,w) {
        if (!found && m[i][j] == '.') {
            found = true;
            queue<pair<int,int>> q;
            q.push(make_pair(i,j));
            next.push(make_tuple(i,j,0));
            while (!q.empty()) {
                int a, b;
                tie(a,b) = q.front();
                q.pop();
                if (m[a][b] == 'S')
                    continue;
                int x[4] = {-1, 0, 1, 0};
                rep (k,4) {
                    int u = a+x[k];
                    int v = b+x[(k+1)%4];
                    if (m[u][v] == '.') {
                        q.push(make_pair(u,v));
                        next.push(make_tuple(u,v,0));
                    }
                }
                m[a][b] = 'S';
            }
        }
    }
    int ans;
    while (!next.empty()) {
        int i, j, dis;
        tie(i,j,dis) = next.front();
        next.pop();
        if (m[i][j] == '.') {
            ans = dis - 1;
            break;
        }
        else if (square[i][j] == INF) {
            square[i][j] = dis;
            int x[4] = {-1, 0, 1, 0};
            rep (k,4) {
                int u = i+x[k];
                int v = j+x[(k+1)%4];
                if (0 <= u && u < h && 0 <= v && v < w && m[u][v] != 'S')
                    next.push(make_tuple(u,v,dis+1));
            }
        }
    }
    cout << ans << endl;
    return 0;
}
0