結果

問題 No.157 2つの空洞
ユーザー hogeover30hogeover30
提出日時 2015-02-27 02:12:59
言語 C++11
(gcc 11.4.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,497 bytes
コンパイル時間 542 ms
コンパイル使用メモリ 66,496 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-06 03:26:21
合計ジャッジ時間 4,118 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int dfs(int, int, int)’:
main.cpp:23:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

ソースコード

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