結果

問題 No.2412 YOU Grow Bigger!
ユーザー keisuke6keisuke6
提出日時 2023-08-11 23:56:33
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 488 ms / 6,000 ms
コード長 1,733 bytes
コンパイル時間 2,429 ms
コンパイル使用メモリ 217,508 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-21 08:46:37
合計ジャッジ時間 9,219 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 487 ms
5,248 KB
testcase_04 AC 488 ms
5,248 KB
testcase_05 AC 404 ms
5,248 KB
testcase_06 AC 417 ms
5,248 KB
testcase_07 AC 486 ms
5,248 KB
testcase_08 AC 402 ms
5,248 KB
testcase_09 AC 387 ms
5,248 KB
testcase_10 AC 137 ms
5,248 KB
testcase_11 AC 27 ms
5,248 KB
testcase_12 AC 3 ms
5,248 KB
testcase_13 AC 209 ms
5,248 KB
testcase_14 AC 133 ms
5,248 KB
testcase_15 AC 199 ms
5,248 KB
testcase_16 AC 292 ms
5,248 KB
testcase_17 AC 198 ms
5,248 KB
testcase_18 AC 153 ms
5,248 KB
testcase_19 AC 85 ms
5,248 KB
testcase_20 AC 45 ms
5,248 KB
testcase_21 AC 62 ms
5,248 KB
testcase_22 AC 185 ms
5,248 KB
testcase_23 AC 104 ms
5,248 KB
testcase_24 AC 240 ms
5,248 KB
testcase_25 AC 91 ms
5,248 KB
testcase_26 AC 107 ms
5,248 KB
testcase_27 AC 70 ms
5,248 KB
testcase_28 AC 162 ms
5,248 KB
testcase_29 AC 303 ms
5,248 KB
testcase_30 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

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