Submission #45514043

---

Source Code Expand

#include <stdio.h>
#include <string.h>

#define INF 1010101010

int H, W, T;
char A[512][512];

int mc[512][512];
int qy[512 * 512], qx[512 * 512];

const int d[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

void bfs(int starty, int startx) {
	int i, j;
	int qs, qe;
	for (i = 0; i < H; i++) {
		for (j = 0; j < W; j++) mc[i][j] = INF;
	}
	mc[starty][startx] = 0;
	qy[0] = starty;
	qx[0] = startx;
	qs = 0;
	qe = 1;
	while (qs < qe) {
		int cy = qy[qs], cx = qx[qs];
		qs++;
		for (i = 0; i < 4; i++) {
			int ny = cy + d[i][0], nx = cx + d[i][1];
			if (0 <= ny && ny < H && 0 <= nx && nx < W && A[ny][nx] != '#') {
				int nc = mc[cy][cx] + 1;
				if (mc[ny][nx] > nc) {
					mc[ny][nx] = nc;
					qy[qe] = ny;
					qx[qe] = nx;
					qe++;
				}
			}
		}
	}
}

int sy = -1, sx = -1, gy = -1, gx = -1;
int kc = 0;
int ky[20], kx[20];
int dists[20][20];

int numBits[1 << 18];

int query;
int memo[18][1 << 20];

int calc(int pos, int visited) {
	int ans = INF;
	int i;
	if (numBits[visited] >= query) return dists[pos][kc + 1];
	if (memo[pos][visited]) return ~memo[pos][visited];
	for (i = 0; i < kc; i++) {
		if (!((visited >> i) & 1)) {
			int candidate = calc(i, visited | (1 << i)) + dists[pos][i];
			if (candidate < ans) ans = candidate;
		}
	}
	return ~(memo[pos][visited] = ~ans);
}

int main(void) {
	int i, j;
	int ok, ng;
	if (scanf("%d%d%d", &H, &W, &T) != 3) return 1;
	for (i = 0; i < H; i++) {
		if (scanf("%511s", A[i]) != 1) return 1;
		for (j = 0; j < W; j++) {
			if (A[i][j] == 'S') { sy = i; sx = j; }
			if (A[i][j] == 'G') { gy = i; gx = j; }
			if (A[i][j] == 'o') {
				ky[kc] = i; kx[kc] = j; kc++;
				if (kc > 18) {
					puts("paiza");
					return 99;
				}
			}
		}
	}
	if (sy < 0 || gy < 0) {
		puts("paiza");
		return 99;
	}
	ky[kc] = sy; kx[kc] = sx;
	ky[kc + 1] = gy; kx[kc + 1] = gx;
	for (i = 0; i <= kc + 1; i++) {	
		bfs(ky[i], kx[i]);
		for (j = 0; j <= kc + 1; j++) {
			dists[i][j] = mc[ky[j]][kx[j]];
		}
	}
	for (i = 0; i < (1 << kc); i++) {
		int cnt = 0, cur = i;
		while (cur > 0) {
			cnt += cur & 1;
			cur >>= 1;
		}
		numBits[i] = cnt;
	}
	ok = -1;
	ng = kc + 1;
	while (ok + 1 < ng) {
		int mid = ok + (ng - ok) / 2;
		memset(memo, 0, sizeof(memo));
		query = mid;
		if (calc(kc, 0) <= T) ok = mid; else ng = mid;
	}
	printf("%d\n", ok);
	return 0;
}

/*

1. 各ポイント間の移動回数を幅優先探索で求める
2. お菓子マスを何個訪れるかを決め打ちし、ビットDP(メモ化探索)で最短移動回数を求める
3. それがT以下かで二分探索する

*/

Submission Info

Judge Result