結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 486 ms
6,944 KB
testcase_04 AC 486 ms
6,944 KB
testcase_05 AC 401 ms
6,940 KB
testcase_06 AC 414 ms
6,944 KB
testcase_07 AC 485 ms
6,944 KB
testcase_08 AC 398 ms
6,944 KB
testcase_09 AC 384 ms
6,940 KB
testcase_10 AC 138 ms
6,940 KB
testcase_11 AC 26 ms
6,940 KB
testcase_12 AC 3 ms
6,940 KB
testcase_13 AC 208 ms
6,940 KB
testcase_14 AC 132 ms
6,944 KB
testcase_15 AC 199 ms
6,940 KB
testcase_16 AC 291 ms
6,940 KB
testcase_17 AC 197 ms
6,940 KB
testcase_18 AC 153 ms
6,944 KB
testcase_19 AC 86 ms
6,940 KB
testcase_20 AC 45 ms
6,944 KB
testcase_21 AC 64 ms
6,940 KB
testcase_22 AC 183 ms
6,940 KB
testcase_23 AC 105 ms
6,940 KB
testcase_24 AC 240 ms
6,944 KB
testcase_25 AC 90 ms
6,940 KB
testcase_26 AC 108 ms
6,940 KB
testcase_27 AC 69 ms
6,940 KB
testcase_28 AC 162 ms
6,944 KB
testcase_29 AC 302 ms
6,944 KB
testcase_30 AC 2 ms
6,940 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