Codeforces Round #139 (Div. 2) D : Snake

問題概要

H*W(H,W<=15)の盤面上でスネークゲームを最短で解く問題。目的地はひとつ、スネークの長さは最大9。

解法

状態数が少ない(15*15*4^8で抑えられる。頭の位置+前からの差分)のでBFSで間に合う。これで十分なんだけどBBでも解ける。ゴールから各マスへの距離を事前にBFSで計算しておき推定値にする。これだけだとTLEするけど、スネークの頭が他の体のいるマスよりもゴールに近いときはゴールまで最短で到達することができることを利用すると反復深化するだけでとける。道が細いときは分岐が少ないし、道が太いときは頭の位置補正がしやすくなる。ちなみにこちらの解法だとスネークの長さが長くても解ける。むしろ長い方が効率的に解ける。

acceptされたコード

データの持ち方変えたらもっと高速化できる。

#include <cstdio>
#include <queue>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

const int INF = int(1.05e9); 
const int MAX_N = 15;
const int MAX_L = 9;
const int dy[] = {1,-1,0,0}, dx[] = {0,0,1,-1};

int H, W, L;
char board[MAX_N][MAX_N + 1];
char cur[MAX_N][MAX_N];
int dist[MAX_N][MAX_N];
int GY, GX, SY, SX;
int ANSWER;


void init() {
	scanf("%d%d", &H, &W);
	for (int i = 0; i < H; ++i ) {
		scanf(" %s ", board[i]);
	}
}

bool dfs(int y, int x, int depth) {
	if (y == GY && x == GX) {
		return true;
	}
	if (depth + dist[y][x] > ANSWER) {
		return false;
	}
	int ds[10];
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			if (isdigit(cur[i][j])) {
				ds[cur[i][j]&15] = dist[i][j];
			}
		}
	}

	bool f = true;
	for (int i = 2; i <= L; ++i) {
		f &= ds[1] <= ds[i];
	}
	if (f) {
		return true;
	}

	char tmp[MAX_N][MAX_N];
	for (int k = 0; k < 4; ++k) {
		const int ny = y + dy[k], nx = x + dx[k];
		if ( 0 <= ny && ny < H && 0 <= nx && nx < W && (cur[ny][nx] == '.' || cur[ny][nx] == '@' || cur[ny][nx] == char(L + '0'))) {
			memcpy(tmp, cur, sizeof(tmp));
			for (int i = 0; i < H; ++i) {
				for (int j = 0; j < W; ++j) {
					if (isdigit(cur[i][j])) {
						if (cur[i][j] < char(L + '0')) {
							++cur[i][j];
						}
						else if(cur[i][j] == char(L + '0')) {
							cur[i][j] = '.';
						}
					}
				}
			}
			cur[ny][nx] = '1';
			if (dfs(ny, nx, depth + 1)) {
				return true;
			}
			memcpy(cur, tmp, sizeof(tmp));
		}
	}
	return false;
}

int solve() {
	for (int i = 0; i < H; ++i) {
		fill(dist[i], dist[i] + W, INF);
		for (int j = 0; j < W; ++j) {
			if (board[i][j] == '@') {
				GY = i;
				GX = j;
			}
			if (isdigit(board[i][j])) {
				L = max(L, board[i][j]&15);
			}
			if (board[i][j] == '1') {
				SY = i;
				SX = j;
			}
		}
	}

	queue< pair<int,int> > que;
	que.push(make_pair(GY, GX));
	dist[GY][GX] = 0;
	for (;!que.empty();) {
		pair<int,int> tp = que.front(); que.pop();
		const int y = tp.first, x = tp.second, d = dist[y][x];
		for (int k = 0; k < 4; ++k) {
			const int ny = y + dy[k], nx = x + dx[k];
			if ( 0 <= ny && ny < H && 0 <= nx && nx < W && board[ny][nx] != '#' && dist[ny][nx] == INF) {
				dist[ny][nx] = d + 1;
				que.push(make_pair(ny, nx));
			}
		}
	}


	if (dist[SY][SX] == INF) {
		return -1;
	}
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			cur[i][j] = board[i][j];
		}
	}

	for (ANSWER = 1;ANSWER < 400; ++ANSWER) {
		if (dfs(SY, SX, 0)) {
			return ANSWER;
		}
	}
	return -1;
}

int main() {
	init();
	printf("%d\n", solve());
	return 0;
}