結果

問題 No.157 2つの空洞
コンテスト
ユーザー s
提出日時 2026-02-15 11:30:43
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 5,051 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,435 ms
コンパイル使用メモリ 285,252 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-02-15 11:30:51
合計ジャッジ時間 6,091 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#define _USE_MATH_DEFINES
#include  <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include<math.h>
#include<iomanip>
#include<stdio.h>
#include <stdlib.h>
#include<stdio.h>
#include <queue>
#include<map>
#include <fstream>
#include <sstream>
#include<set>
#include<stack>
#include<time.h>
#include <sys/types.h>
#include <tuple>
#include <numeric>
#include <iterator>
#include <atcoder/all>

#include <bits/stdc++.h>
// 128bit整数を扱うための型


#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace atcoder;
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
typedef modint1000000007 mint;




ll gcd(ll a, ll b) {
    if (a < b)swap(a, b);
    if (b == 0)return a;

    return gcd(b, a % b);
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

/*
解説動画参考
解説ブログ参考


*/
long long integer_sqrt(ll n) {
    if (n < 0) return -1;
    if (n == 0) return 0;
    long long res = sqrt((double)n);
    // 精度補正
    while ((ll)(res + 1) * (res + 1) <= n) res++;
    while ((ll)res * res > n) res--;
    return res;
}



struct UnionFind {
    std::vector<int> parent; // 親の番号（自身が根の場合は負の数でグループサイズを表す）
    //vector<int> black_count;
    vector<int>fill;
    // 初期化: 最初は全員が根（サイズ1なので -1 で初期化）
    //UnionFind(int n) : parent(n, -1) {}
    
    UnionFind(int n) {
        parent.assign(n + 1, -1);
        //black_count.assign(n + 1, 0);
        fill.assign(n + 1, 0);
    }
    
    // Find: 根を探す（経路圧縮付き）
    int find(int x) {
        if (parent[x] < 0) return x; // 負の数なら自分が根
        return parent[x] = find(parent[x]); // 経路圧縮：親を根に直接つなぎ替える
    }

    // Union: グループを合体させる（サイズによる併合）
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false; // すでに同じグループ

        // 大きい方（サイズが負で値が小さい方）に小さい方をくっつける
        if (parent[x] > parent[y]) std::swap(x, y);
        parent[x] += parent[y]; // サイズを合算
        parent[y] = x;          // yの親をxにする

        //black_count[x] += black_count[y];

        return true;
    }

    // 同じグループに属しているか判定
    bool same(int x, int y) {
        return find(x) == find(y);
    }

    // グループのサイズを返す
    int size(int x) {
        return -parent[find(x)];

    }
    void fill_sl(int x) {
        int r = find(x);
        fill[r]++;
    }
    int get_count(int x) {
        return fill[find(x)];
    }

/*
    void update_color(int v, int diff) {
        int r = find(v);
        black_count[r] += diff;
    }
    int get_black_count(int v) {
        int r = find(v);
        return black_count[r];
    }
    */
};
ll calc_score(vector<int>v) {
    ll sc = 0;
    for (int i = 1; i <= 9;i++) {
        ll p = i;
        for (int j = 0; j < v[i]; j++)p *= 10;
        sc += p;
    }
    return sc;
}



int main()
{

    int Q;
    Q = 1;
    //cin >> Q;


    while (Q--) {
        int m;
        cin >> m;
        int n;
        cin >> n;
        vector<string>p(n);
        for (int i = 0; i < n; i++)cin >> p[i];
        int c[25][25] = {};
        int g = 1;
       
        vector<pair<int, int>>p1, p2;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (p[i][j] == '#')continue;
                if (c[i][j])continue;
                queue<int>x, y;
                x.push(i);
                y.push(j);
                c[i][j] = g;
                
                
                while (x.size()) {
                    
                    int a = x.front();
                    int b = y.front();
                    if (g == 1)p1.push_back({ a,b });
                    else p2.push_back({ a,b });
                    x.pop(); y.pop();
                  
                    int dx[6] = { 0,0,1,-1 };
                    int dy[6] = { 1,-1,0,0 };
                    for (int k = 0; k < 4; k++) {
                        int nx = dx[k] + a;
                        int ny = dy[k] + b;
                        
                        if (nx < 0 || ny < 0 || nx >= n || ny >= m)continue;
                        if (p[nx][ny] == '#')continue;
                        if (c[nx][ny])continue;
                        
                        c[nx][ny] = g;
                        x.push(nx); y.push(ny);



                    }




                }
                g++;
            }
        }
        int ans = 1e5;
        for (int i = 0; i < p1.size(); i++) {
            for (int j = 0; j < p2.size(); j++) {
                int t = abs(p1[i].first - p2[j].first) + abs(p1[i].second - p2[j].second) - 1;
                ans = min(ans, t);
            }
        }
        cout << ans << endl;




    }

    return 0;
}
0