結果

問題 No.157 2つの空洞
コンテスト
ユーザー kohei2019
提出日時 2021-08-30 19:24:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 4,002 bytes
コンパイル時間 2,643 ms
コンパイル使用メモリ 211,644 KB
最終ジャッジ日時 2025-01-24 04:06:13
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using PAIR = pair<int, int>;
using PAIRLL = pair<ll,ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vs = vector<string>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define INF 100000000
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x:コンテナ
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//定数
#define INF32 2147483647 //2.147483647×10^{9}:32bit整数のinf
#define INF64 9223372036854775807 //9.223372036854775807×10^{18}:64bit整数のinf
#define MOD 1000000007 //問題による
#define F first
#define S second
//出力(空白区切りで昇順に)
#define coutALL(x) for(auto i=x.begin();i!=--x.end();i++)cout<<*i<<" ";cout<<*--x.end()<<endl
#define coutALLn(x) for(auto i=x.begin();i!=--x.end();i++)cout<<*i<<endl;cout<<*--x.end()<<endl
ll myceil(ll a,ll b){return (a+(b-1))/b;}
ll myfloor(ll a,ll b){return a/b;}

int main(){
    int W,H;
    cin >> W >> H;
    vector<string> lsHW(H);
    rep(i,H) cin >> lsHW[i];
    deque<pair<int,int>> d;
    deque<pair<int,int>> d1;
    vector<pair<int,int>> ls1;
    vector<vector<bool>> used(H,vector<bool>(W,false));
    vector<vector<bool>> used1(H,vector<bool>(W,false));
    vector<vector<int>> lscost(H,vector<int>(W,INF32));
    vector<int> dx = {1,-1,0,0};
    vector<int> dy = {0,0,1,-1};
    int x,y;
    pair<int,int> c;

    bool f = false;
    rep(i,H){
        rep(j,W){
            if (lsHW[i][j] == '.'){
                d.push_back({i,j});
                d1.push_back({i,j});
                lscost[i][j] = 0;
                f = true;
                break;
                }
        }
        if (f){
            break;
        }
    }
    while (d1.empty() == false){
        c = d1.front();
        d1.pop_front();
        d.push_back(c);
        ls1.push_back(c);
        x = c.first;
        y = c.second;
        if (used1[x][y]){
            continue;
        }
        used1[x][y] = true;
        rep(i,4){
            int nextx = x+dx[i];
            int nexty = y+dy[i];
            if (0<=nextx && nextx<H && 0<=nexty && nexty<W){
                if (used1[nextx][nexty]){
                    continue;
                }
                if (lsHW[nextx][nexty] == '.'){
                    if (lscost[nextx][nexty] > lscost[x][y]){
                        lscost[nextx][nexty] = lscost[x][y];
                        d1.push_front({nextx,nexty});
                    }
                }
                
            }
        }
    }

    while (d.empty() == false){
        c = d.front();
        d.pop_front();
        x = c.first;
        y = c.second;
        if (used[x][y]){
            continue;
        }
        used[x][y] = true;
        rep(i,4){
            int nextx = x+dx[i];
            int nexty = y+dy[i];
            if (0<=nextx && nextx<H && 0<=nexty && nexty<W){
                if (used[nextx][nexty]){
                    continue;
                }
                if (lsHW[nextx][nexty] == '#'){
                    if (lscost[nextx][nexty] > lscost[x][y]+1){
                        lscost[nextx][nexty] = lscost[x][y]+1;
                        d.push_back({nextx,nexty});
                    }
                }
                if (lsHW[nextx][nexty] == '.'){
                    if (lscost[nextx][nexty] > lscost[x][y]){
                        lscost[nextx][nexty] = lscost[x][y];
                        d.push_front({nextx,nexty});
                    }
                }
                
            }
        }
    }

    for (const auto & p:ls1){
        x = p.first;
        y = p.second;
        lsHW[x][y] = '#';
    }
    rep(i,H){
        rep(j,W){
            if (lsHW[i][j] == '.'){
                cout << lscost[i][j] << endl;
                return 0;
            }    
        }
    }
}
0