結果

問題 No.157 2つの空洞
ユーザー phspls
提出日時 2020-04-08 23:11:02
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,023 bytes
コンパイル時間 1,555 ms
コンパイル使用メモリ 172,180 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-19 05:48:48
合計ジャッジ時間 2,246 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define llong long long

vector<pair<int, int>> pool1;
vector<pair<int, int>> pool2;
int w, h;

void dfs(vector<string> &mapping, int y, int x, bool ispool1) {
    if(!(0 <= y && y < h && 0 <= x && x < w)) return;
    if(mapping[y][x] == '#') return;
    mapping[y][x] = '#';
    if(ispool1) pool1.push_back(make_pair(y, x));
    else pool2.push_back(make_pair(y, x));
    
    dfs(mapping, y-1, x, ispool1);
    dfs(mapping, y+1, x, ispool1);
    dfs(mapping, y, x-1, ispool1);
    dfs(mapping, y, x+1, ispool1);
}

int main() {
    cin >> w >> h;
    vector<string> mapping(h);
    rep(i, h) cin >> mapping[i];

    rep(i, h)
        rep(j, w)
            dfs(mapping, i, j, pool1.empty());

    int dist = 20*20;
    for(pair<int, int> p1: pool1) {
        for(pair<int, int> p2: pool2) {
            dist = min(dist, abs(p1.first - p2.first) + abs(p1.second - p2.second) - 1);
        }
    }
    cout << dist << "\n";
}
0