結果

問題 No.157 2つの空洞
コンテスト
ユーザー hogeover30
提出日時 2015-02-27 02:12:59
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,497 bytes
コンパイル時間 607 ms
コンパイル使用メモリ 67,124 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-23 22:18:10
合計ジャッジ時間 4,473 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 4
other RE * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int dfs(int, int, int)’:
main.cpp:23:1: warning: no return statement in function returning non-void [-Wreturn-type]
   23 | }
      | ^

ソースコード

diff # 

#include <iostream>
#include <string>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;

string C[30];
int W, H;

int a[30][30], b[30][30];
int dr[]={-1, 0, 1, 0}, dc[]={0, -1, 0, 1};

int dfs(int r, int c, int k)
{
    a[r][c]=k;
    for(int i=0;i<4;++i) {
        int nr=r+dr[i], nc=c+dc[i];
        if (nr<0 or nr>=H or nc<0 or nc>=W) continue;
        if (C[nr][nc]=='#' or a[nr][nc]) continue;
        dfs(nr, nc, k);
    }
}

int main()
{
    while (cin>>W>>H) {
        for(int i=0;i<H;++i) cin>>C[i];

        memset(a, 0, sizeof(a));
        int k=0;
        for(int i=0;i<H;++i) for(int j=0;j<W;++j)
            if (C[i][j]=='.' and !a[i][j]) dfs(i, j, ++k);

        memset(b, -1, sizeof(b));
        queue<pair<int, int>> q;
        for(int i=0;i<H;++i) for(int j=0;j<W;++j) {
            if (a[i][j]==1 and (!a[i][j+1] or !a[i+1][j] or !a[i-1][j] or !a[i][j-1])) {
                q.emplace(i, j);
                b[i][j]=0;
            }
        }
        int res=0;
        while (q.size()) {
            auto p=q.front(); q.pop();
            int r=p.first, c=p.second;
            if (a[r][c]==2) { res=b[r][c]-1; break; }
            for(int i=0;i<4;++i) {
                int nr=r+dr[i], nc=c+dc[i];
                if (nr<0 or nr>=H or nc<0 or nc>=W) continue;
                if (b[nr][nc]>=0 or a[nr][nc]==1) continue;
                q.emplace(nr, nc);
                b[nr][nc]=b[r][c]+1;
            }
        }
        cout<<res<<endl;
    }
}
0