SRM588 D1-Hard GameInDarknessDiv1

TopCoder

問題

2次元上のn*mセルからなる盤面にアリスとボブのトークンが1つずつ配置されている。盤面には壁があり、壁でないセルの隣接関係をグラフにすると木になっている。
アリスとボブが交互にトークンを隣接したセルに移動させる。もしアリスとボブのトークンが同じセルに入るとアリスの勝ち、100000手逃げ切ることができればボブの勝ちとなる。
ただし、アリスには双方の初期位置しかわからず、ボブの移動経路は知ることができない。また、ボブはアリスがゲーム中にどのようにトークンを移動させるかがすべてわかっている。
この条件のもとで、双方が最善な手を取った時にどちらが勝利するかを求めよ。

  • 2 <= n, m <= 50

解法

（System Testは通せたもののちゃんと証明できていないので嘘解法かも）
盤面が十分に小さいので100000手逃げ切ることができる→永遠に逃げ続けられると考える。
ボブがアリスから逃げ切るためには、その頂点を取り除いたときに、もともとそれと隣接していた頂点を根とした木の深さが3以上となる頂点が3つ以上ある頂点に、アリスより2手早く到達する必要がある。
そのような条件を満たす頂点が存在するならボブが勝ち、存在しなければアリスが勝つ。

コード

const int INF = 1000000000;
const int dx[] = { 1, 0, -1, 0 };
const int dy[] = { 0, -1, 0, 1 };

bool between(int a, int b, int c){
	return a <= b && b < c;
}

class GameInDarknessDiv1 {
	bool dfs(int d, int u, int p, const vector< vector<int> > &conn) const {
		if(d == 0){ return true; }
		for(int i = 0; i < conn[u].size(); ++i){
			const int v = conn[u][i];
			if(v == p){ continue; }
			if(dfs(d - 1, v, u, conn)){ return true; }
		}
		return false;
	}
	vector<int> bfs(int root, const vector< vector<int> > &conn) const {
		const int n = conn.size();
		vector<int> dist(n, INF);
		dist[root] = 0;
		queue<int> q;
		q.push(root);
		while(!q.empty()){
			const int u = q.front();
			q.pop();
			for(int i = 0; i < conn[u].size(); ++i){
				const int v = conn[u][i];
				if(dist[v] < INF){ continue; }
				dist[v] = dist[u] + 1;
				q.push(v);
			}
		}
		return dist;
	}
public:
	string check(vector <string> field){
		const int n = field.size(), m = field[0].size();
		vector< vector<int> > id(n, vector<int>(m, -1));
		int k = 0, ai = 0, bi = 0;
		for(int i = 0; i < n; ++i){
			for(int j = 0; j < m; ++j){
				if(field[i][j] == '#'){ continue; }
				if(field[i][j] == 'A'){ ai = k; }
				if(field[i][j] == 'B'){ bi = k; }
				id[i][j] = k++;
			}
		}
		vector< vector<int> > conn(k);
		for(int i = 0; i < n; ++i){
			for(int j = 0; j < m; ++j){
				if(id[i][j] < 0){ continue; }
				for(int d = 0; d < 4; ++d){
					const int y = i + dy[d], x = j + dx[d];
					if(!between(0, y, n) || !between(0, x, m)){ continue; }
					if(id[y][x] < 0){ continue; }
					conn[id[i][j]].push_back(id[y][x]);
				}
			}
		}
		vector<int> adist = bfs(ai, conn), bdist = bfs(bi, conn);
		if(adist[bi] <= 1){ return "Alice wins"; }
		for(int i = 0; i < k; ++i){
			if(conn[i].size() < 3){ continue; }
			int num = 0;
			for(int j = 0; j < conn[i].size(); ++j){
				if(dfs(2, conn[i][j], i, conn)){ ++num; }
			}
			if(num >= 3){
				if(adist[i] > bdist[i] + 1){
					return "Bob wins";
				}
			}
		}
		return "Alice wins";
	}
};