結果

問題 No.157 2つの空洞
コンテスト
ユーザー wunderkammer2
提出日時 2021-06-24 22:24:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 5,975 bytes
コンパイル時間 1,605 ms
コンパイル使用メモリ 134,164 KB
最終ジャッジ日時 2025-01-22 11:47:48
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 RE * 1
other AC * 10 RE * 6
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int calc(int, int, vs&, UnionFind&)’:
main.cpp:208:1: warning: control reaches end of non-void function [-Wreturn-type]
  208 | }
      | ^

ソースコード

diff # 

#include<algorithm>     //sort,二分探索,など
#include<bit>           //popcount
#include<bitset>        //固定長bit集合
#include<cmath>         //pow,logなど
#include<complex>       //複素数
#include<deque>         //両端アクセスのキュー
#include<fstream>       //ファイルストリーム（標準入力変更用）
#include<functional>    //sortのgreater
#include<iomanip>       //setprecision(浮動小数点の出力の誤差)
#include<iostream>      //入出力
#include<iterator>      //集合演算(積集合,和集合,差集合など)
#include<map>           //map(辞書)
#include<numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include<queue>         //キュー
#include<set>           //集合
#include<stack>         //スタック
#include<string>        //文字列
#include<unordered_map> //イテレータあるけど順序保持しないmap
#include<unordered_set> //イテレータあるけど順序保持しないset
#include<utility>       //pair
#include<vector>        //可変長配列

//#include<atcoder\all>
//using namespace atcoder;

//名前
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef map<string, int> msi;
typedef map<string, ll> msll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pllll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<string>> vvs;
typedef vector<vector<bool>> vvb;

//定数
const ll MOD = 1000000007;
const ll INF = 1000000000000000000;
const int MAXR = 100000;             //10^5:配列の最大のrange

//マクロ
#define rep(i,n) for(int i=0;i<n;i++)
#define reps(i,s,e) for(int i=s;i<e;i++)
#define repse(i,s,e) for(int i=s;i<=e;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define in1(x1) cin >> x1
#define in2(x1, x2) cin >> x1 >> x2
#define in3(x1, x2, x3) cin >> x1 >> x2 >> x3
#define in4(x1, x2, x3, x4) cin >> x1 >> x2 >> x3 >> x4
#define in5(x1, x2, x3, x4, x5) cin >> x1 >> x2 >> x3 >> x4 >> x5
#define in6(x1, x2, x3, x4, x5, x6) cin >> x1 >> x2 >> x3 >> x4 >> x5 >> x6
#define inN(x, N) rep(i, N) in1(x[i])
#define outl(x) cout << x << endl
#define out2l(x, y) cout << x << " " << y << endl
#define out3l(x1, x2, x3) cout << x1 << " " << x2 << " " << x3 << endl
#define out4l(x1, x2, x3, x4) cout << x1 << " " << x2 << " " << x3 << " " << x4 << endl
#define outList(x) for(auto y : x) cout << y << " ";cout << endl

//よく使う関数
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
inline ll div_ceil(ll a, ll b) { return (a + (b - 1)) / b; }
inline string zeropad(int n, int m) { ostringstream sout; sout << setfill('0') << setw(m) << n; return sout.str(); }


class UnionFind
{
	//par[i]：ノードiの親
	//count[i]：iが親の時、iが属するグループのノード数
	vector<int> par;
	vector<int> count;

	int m_groupCount = 0;

public:
	UnionFind(int N)
	{
		//1始まりのときに必要
		//par.push_back(0);
		//count.push_back(0);

		m_groupCount = N;

		rep(i, N)
		{
			//最初は全てが根であるとして初期化
			par.push_back(i);
			count.push_back(1);
		}
	}

	//データxが属する木の根を再帰で得る：root(x) = {xの木の根}
	int root(int x)
	{
		if (par[x] == x) return x;

		//ついでに親を張り替え
		return par[x] = root(par[x]);
	}

	//xとyの木を併合
	void unite(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		if (rx == ry) return;
		//xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
		par[rx] = ry;

		//要素数の変更
		count[ry] += count[rx];
		count[rx] = 0;

		//木の併合によってグループが1つ減る
		m_groupCount--;
	}

	// 2つのデータx, yが属する木が同じならtrueを返す
	bool same(int x, int y)
	{
		return root(x) == root(y);
	}

	//指定したデータxが属するグループの要素数を返す
	int size(int x)
	{
		return count[root(x)];
	}

	//UnionFindのグループの個数を返す
	int groupCount()
	{
		return m_groupCount;
	}

	//UnionFindのコピー処理
	UnionFind copy()
	{
		UnionFind uf(par.size());

		//元のUnionFindの親情報を再現
		rep(i, par.size())
		{
			uf.unite(i, this->root(i));
		}

		return uf;
	}
};


int H, W;

int rctoi(int h, int w)
{
	return h * W + w;
}

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

int calc(int h, int w, vs &C, UnionFind &uf)
{
    queue<pii> q;
    q.emplace(h, w);

    vvi d(H, vi(W, -1));
    d[h][w] = 0;

    while (!q.empty())
    {
        auto p = q.front(); q.pop();

        rep(i, 4)
        {
            int x = p.first + dx[i];
            int y = p.second + dy[i];

            if (!(x >= 0 && x < H && y >= 0 && y < W)) continue;

			if (d[x][y] != -1) continue;

            if(uf.same(rctoi(h, w), rctoi(x, y))) continue;

            q.emplace(x, y);
			d[x][y] = d[p.first][p.second];
			if (C[x][y] == '.')
			{
				return d[x][y];
			}
			else
			{
				d[x][y]++;
			}
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    //標準入力をファイルに変更
    //std::ifstream in("input.txt");
    //std::cin.rdbuf(in.rdbuf());
    
    in2(W, H);

    vs C(H);
    inN(C, H);

	UnionFind uf(H * W);

	rep(i, H) rep(j, W) rep(k, 4)
	{
		int x = i + dx[k];
		int y = j + dy[k];

		if (!(x >= 0 && x < H && y >= 0 && y < W)) continue;

		if (C[i][j] == C[x][y]) uf.unite(rctoi(i, j), rctoi(x, y));
	}


    int ans = numeric_limits<int>().max();

    rep(i, H) rep(j, W)
    {
        if (C[i][j] == '.')
        {
            chmin(ans, calc(i, j, C, uf));
        }
    }

    outl(ans);

    return 0;
}
0