人材獲得作戦・４を自分なりに解いてみた

現在競技プログラミング界隈でプチ炎上中のこの問題を解いてみた。解答に20分。途中バグに悩まされて大幅に時間をロスした。正直修行が足りないと思う。
この問題を解いていて感じたことは、この会社は基本レベルがクリアできている人が欲しいんだろうなぁという点。この問題はドラクエマップ上の幅優先探索で、ICPCやTopCoderでは基本中の基本問題。この問題が解けることによって分かる事は「テキスト入出力がプログラムで書ける」「プログラムでループが書ける」「幅優先探索等の基本的な探索手法がプログラムで書ける」という基本的なもの。これらが3時間以内に書ければ試験に通り、そういう試験に通る人が欲しいのだと勝手に解釈した。
ICPCやTopCoderで出題されるときは、コレに色をつけて出されたりする。例えば途中に毒の沼地と回復ゾーンがあってHPが0にならないように進むだとか、スイッチで開閉する扉があるだとか、ワープゾーンがあるだとか、何回まで壁を壊せるだとか、双子の冒険者が二つのマップ上で左右対称の動きをするだとか、進行方向を変えた回数を最小化するだとか・・・。自分としてはそういう色気の付いた問題を解いていた方が面白いと感じる。
こう感じるのは自分が競技プログラミング大好き人間だからだろうか？

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

int main()
{
	vector<string> maze;
	string line;
	while (getline(cin, line)) {
		maze.push_back(line);
	}

	const int W = maze.size();
	const int H = maze[0].size();

	int startX, startY, goalX, goalY;
	for (int x = 0; x < W; ++x) {
		for (int y = 0; y < H; ++y) {
			if (maze[x][y] == 'S') {
				startX = x;
				startY = y;
			} else if (maze[x][y] == 'G') {
				goalX = x;
				goalY = y;
			}
		}
	}

	static int prevX[1024][1024];
	static int prevY[1024][1024];
	static bool dp[1024][1024];
	prevX[startX][startY] = -1;
	prevY[startX][startY] = -1;
	memset(dp, 0, sizeof(dp));
	dp[startX][startY] = true;

	deque<int> q;
	q.push_back(startX);
	q.push_back(startY);

	while (!q.empty()) {
		const int x = q.front();
		q.pop_front();
		const int y = q.front();
		q.pop_front();

		for (int dir = 0; dir < 4; ++dir) {
			const int nextX = x + dx[dir];
			const int nextY = y + dy[dir];

			if (maze[nextX][nextY] == '*' || dp[nextX][nextY]) {
				continue;
			}

			q.push_back(nextX);
			q.push_back(nextY);
			prevX[nextX][nextY] = x;
			prevY[nextX][nextY] = y;
			dp[nextX][nextY] = true;
		}
	}

	int x = goalX;
	int y = goalY;
	while (x != -1) {
		if (maze[x][y] == ' ') {
			maze[x][y] = '$';
		}
		const int nextX = prevX[x][y];
		const int nextY = prevY[x][y];
		x = nextX;
		y = nextY;

		cout << x << " " << y << endl;
	}

	for (vector<string>::iterator it = maze.begin(); it != maze.end(); ++it) {
		cout << *it << endl;
	}
}

人生を書き換える者すらいた。: 人材獲得作戦・４　試験問題ほか
http://okajima.air-nifty.com/b/2010/01/post-abc6.html