結果

問題 No.157 2つの空洞
コンテスト
ユーザー Naco
提出日時 2019-07-16 01:20:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,683 bytes
コンパイル時間 911 ms
コンパイル使用メモリ 75,520 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-28 10:26:15
合計ジャッジ時間 2,112 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:73:9: warning: 'sy' may be used uninitialized [-Wmaybe-uninitialized]
   73 |     bfs1(sx,sy);
      |     ~~~~^~~~~~~
main.cpp:64:12: note: 'sy' was declared here
   64 |     int sx,sy;
      |            ^~
main.cpp:73:9: warning: 'sx' may be used uninitialized [-Wmaybe-uninitialized]
   73 |     bfs1(sx,sy);
      |     ~~~~^~~~~~~
main.cpp:64:9: note: 'sx' was declared here
   64 |     int sx,sy;
      |         ^~

ソースコード

diff # 

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

typedef pair<int,int> P;

static const int MAX=25;

int W,H;
char C[MAX][MAX];
int d[MAX][MAX];
bool used[MAX][MAX]={};

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

int ans=1000000000;

void bfs1(int sx,int sy){
    queue<P> que;
    que.push(P(sx,sy));
    used[sx][sy]=true;
    while(!que.empty()){
        P p=que.front(); que.pop();
        for(int i=0;i<4;i++){
            int nx=p.first+dx[i];
            int ny=p.second+dy[i];
            if(nx>=0&&nx<H&&ny>=0&&ny<W&&used[nx][ny]==false&&C[nx][ny]=='.'){
                used[nx][ny]=true;
                que.push(P(nx,ny));
            }
        }
    }
}

void bfs2(){
    queue<P> que;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            d[i][j]=-1;
            if(C[i][j]=='.'&&used[i][j]==true){
                d[i][j]=0;
                que.push(P(i,j));
            }
        }
    }
    while(!que.empty()){
        P p=que.front(); que.pop();
        for(int i=0;i<4;i++){
            int nx=p.first+dx[i];
            int ny=p.second+dy[i];
            if(nx>=0&&nx<H&&ny>=0&&ny<W&&d[nx][ny]==-1&&C[nx][ny]=='#'){
                d[nx][ny]=d[p.first][p.second]+1;
                que.push(P(nx,ny));
            }else if(nx>=0&&nx<H&&ny>=0&&ny<W&&d[nx][ny]==-1&&C[nx][ny]=='.'){
                ans=min(ans,d[p.first][p.second]);
            }
        }
    }
}

int main(){
    cin >> W >> H;
    int sx,sy;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin >> C[i][j];
            if(C[i][j]=='.'){
                sx=i,sy=j;
            }
        }
    }
    bfs1(sx,sy);
    bfs2();
    cout << ans << endl;
}
0