ICPC2017 国内予選 G 迷宮を一周

AOJ ICPC グラフ理論

問題

日本語なので略
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1622&lang=jp

解法

フローだと思ってどうも答えがあわず結局自力で解けなかったので平石さんという方の書いた（http://www.cse.kyoto-su.ac.jp/~hiraishi/ICPC/ICPC2017/Domestic/ICPC2017_Domestic.pdf）答え見た。


迷路をグリッドグラフとしてみる。入口と宝のあるセルの合計4つのセルのノードを通る単純閉路があればよい。
最も単純な方法として、

  • 4つのノードがグラフ上で連結
  • グラフからどれか1つのノードを取り除いて4つのノードが非連結になるようなノードが存在しない

が成り立てば単純閉路がある。
グラフが小さいのでこれで間に合う。


たぶんフロー解法はダメ。フローで解けた人いたら教えて下さい。
自分がやろうとしたのは

  • 各セルをIN, OUTに分割してIN, OUTに容量1の辺を張り、
  • 左下から右上の部屋に流量2のフローが流れるかを見る、
  • ただし右上左下の部屋は最低1の流量が流れないとだめという下限制約をつける。

という方針だけど、これだと右上の部屋からループだけするフローみたいなもので下限制約が満たされてしまうのでだめだった。

ソースコード

const int dy[] = {0, -1, 0, 1}, dx[] = {-1, 0, 1, 0};
int n, m;
string in[100];
bool v[50][50];

void rec(int y, int x){
	v[y][x] = 1;
	rep(d, 4){
		int ny = y + dy[d], nx = x + dx[d];
		if(ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
		if(v[ny][nx] || in[ny][nx] == '#') continue;
		rec(ny, nx);
	}
}
bool con_check(){
	memset(v, 0, sizeof(v));
	rec(0, 0);
	return v[0][m - 1] && v[n - 1][0] && v[n - 1][m - 1];
}
int main(){
	while(cin >> n >> m, n){
		rep(i, n) cin >> in[i];
		
		bool found = 0;
		if(!con_check()){
			found = 1;
			goto END;
		}
		rep(y, n) rep(x, m) if(in[y][x] == '.'){
			if(y==0 && x==0 || y==0 && x==m-1 || y==n-1 && x==0 || y==n-1 && x==m-1) continue;
			in[y][x] = '#';
			if(!con_check()){ found = 1; goto END; }
			in[y][x] = '.';
		}
		END:
		cout << (found ? "NO" : "YES") << endl;
	}
	return 0;
}