結果

問題 No.2412 YOU Grow Bigger!
コンテスト
ユーザー keisuke6
提出日時 2023-08-11 23:56:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 302 ms / 6,000 ms
コード長 1,733 bytes
コンパイル時間 1,872 ms
コンパイル使用メモリ 211,380 KB
最終ジャッジ日時 2025-02-16 02:27:30
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct Unionfind{
  vector<int> par, siz;
  //初期化
  Unionfind(int n) : par(n,-1) , siz(n,1) {}
  int root(int x) {
    if(par[x] == -1) return x;
    else return par[x] = root(par[x]);
  }
  bool issame(int x,int y) {
    return root(x) == root(y);
  }
  bool unite(int x, int y){
    x = root(x); y = root(y);
    if(x ==  y) return false;
    if(siz[x] < siz[y]) swap(x,y);
    par[y] =  x;
    siz[x] += siz[y];
    return  true;
  }
  int size(int x) {
    return siz[root(x)];
  }
};
signed main(){
	int H,W;
	cin>>H>>W;
	vector<vector<char>> S(H,vector<char>(W));
	for(int i=0;i<H;i++)for(int j=0;j<W;j++) cin>>S[i][j];
	vector<vector<bool>> A(H-2,vector<bool>(W-2,true));
	for(int i=0;i<H-2;i++)for(int j=0;j<W-2;j++)for(int k=0;k<3;k++)for(int l=0;l<3;l++)if(S[i+k][j+l] == '#') A[i][j] = false;
	int ans = 2;
	for(int i=0;i<H;i++)for(int j=0;j<W;j++){
		if((i < 3 && j < 3) || (i >= H-3 && j >= W-3)) continue;
		vector<vector<bool>> B = A;
		for(int k=-2;k<=0;k++)for(int l=-2;l<=0;l++)if(i+k >= 0 && j+l >= 0 && i+k+2 < H && j+l+2 < W) B[i+k][j+l] = false;
		Unionfind uf((H-2)*(W-2));
		for(int k=0;k<H-2;k++)for(int l=0;l<W-2;l++)for(int x=-1;x<=1;x++)for(int y=-1;y<=1;y++){
			if(k+x >= 0 && k+x < H-2 && l+y >= 0 && l+y < W-2 && B[k][l] && B[k+x][l+y]) uf.unite(k*(W-2)+l,(k+x)*(W-2)+(l+y));
		}
		if(!uf.issame(0,(H-2)*(W-2)-1)) ans = 1;
	}
	Unionfind uf((H-2)*(W-2));
	for(int k=0;k<H-2;k++)for(int l=0;l<W-2;l++)for(int x=-1;x<=1;x++)for(int y=-1;y<=1;y++){
		if(k+x >= 0 && k+x < H-2 && l+y >= 0 && l+y < W-2 && A[k][l] && A[k+x][l+y]) uf.unite(k*(W-2)+l,(k+x)*(W-2)+(l+y));
	}
	if(!uf.issame(0,(H-2)*(W-2)-1)) ans = 0;
	cout<<ans<<endl;
}
0