PKU 3009 Curling 2.0

• 深さ優先探索
• 幅優先探索と見せかけておいて、実は最大10手まで
• 4^10=2^20で通ってしまう

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int maze[32][32];
int w, h;
int answer;

bool in(int x, int y) {
	return 0 <= x && x < w && 0 <= y && y < h;
}

void dfs(int x, int y, int step) {
	if (step >= answer) {
		return;
	}

	for (int dir = 0; dir < 4; ++dir) {
		int nx = x + dx[dir];
		int ny = y + dy[dir];
		bool goal = false;

		if (!in(nx, ny) || maze[nx][ny] == 1) {
			continue;
		}

		for (;;) {
			if (!in(nx, ny)) {
				// 外に飛び出たら止める
				break;

			} else if (maze[nx][ny] == 1) {
				// 壁にぶつかったら止める
				break;

			} else if (maze[nx][ny] == 3) {
				// ゴールにたどり着いたら答えを更新して即return
				if (answer > step) {
					answer = step;
					return;
				}
			}

			nx += dx[dir];
			ny += dy[dir];
		}

		if (!in(nx, ny)) {
			continue;
		}

		// 壁にぶつかった
		maze[nx][ny] = 0;
		dfs(nx - dx[dir], ny - dy[dir], step + 1);
		maze[nx][ny] = 1;
	}
}

int main() {
	for (; cin >> w >> h && (w || h); ) {
		int startX, startY;
		for (int y = 0; y < h; ++y) {
			for (int x = 0; x < w; ++x) {
				cin >> maze[x][y];

				if (maze[x][y] == 2) {
					startX = x;
					startY = y;
				}
			}
		}

		answer = 11;

		dfs(startX, startY, 1);

		if (answer == 11) {
			answer = -1;
		}

		cout << answer << endl;
	}
}