Codeforces 193A Cutting Figure

問題

n行m列のグリッドが与えられる。各マスは'.'または'#'である。
#のマスが連結であるとは、「どの二つの#のマスも、辺を共有するような'#'を経由してたどり着ける」ことを言う。
#が一つだけのグリッド、#が一つもないグリッドは連結であることに注意する。

与えられたグリッドの'#'のマスを自由に'.'に変更することができるとき、
#のマスを連結でなくするために変更しなければならないマスの個数の最小値を求めよ。
どうやっても不可能な場合は-1を出力せよ。

制約条件

n, m≦50
与えられたグリッドが最初連結であることは保証されている。
また、与えられたグリッドは一つ以上の'#'を含む。

方針

角にある#のマスを考える。
最悪でも隣にある二つのマスを消せば、そのマスは非連結にできる。
したがって、答えは最大でも2である。

ということは、1マス消して非連結にできるかを確かめればよいが、
それは全探索して間に合う。

どうやっても非連結にできない場合は-1を出力するが、
これは、与えられたグリッドに含まれる#の数が0, 1, 2であることが必要十分条件。
（3つ以上なら角を分離させればよいから）

ソースコード

int h, w;
string in[50];
bool v[50][50];

void dfs(int y, int x){
	v[y][x] = 1;
	rep(d, 4){
		const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
		int ny = y + dy[d], nx = x + dx[d];
		if(ny < 0 || nx < 0 || ny >= h|| nx >= w || in[ny][nx] != '#' || v[ny][nx]) continue;
		dfs(ny, nx);
	}
}

bool check(){
	memset(v, 0, sizeof(v));
	int cnt = 0;
	rep(i, h) rep(j, w) if(in[i][j] == '#' && !v[i][j]) dfs(i, j), cnt++;
	return cnt > 1;
}

int main(){
	cin >> h >> w;
	rep(i, h) cin >> in[i];
	
	int cnt = 0;
	rep(i, h) rep(j, w) if(in[i][j] == '#') cnt++;
	if(cnt < 3){
		cout << -1 << endl;
		return 0;
	}
	
	rep(i, h) rep(j, w) if(in[i][j] == '#'){
		in[i][j] = '.';
		if(check()){
			cout << 1 << endl;
			return 0;
		}
		in[i][j] = '#';
	}
	cout << 2 << endl;
	
	return 0;
}