Submission #70669896

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <string.h>
int H, W;
char S[16][16];
int gomi_cnt[16][16];
/* [offset_y][offset_x][alive_y][dead_y][alive_x][dead_x] */
int mincost[32][32][16][16][16][16];
struct status_s {
  int offset_y, offset_x, alive_y, dead_y, alive_x, dead_x;
};
int* status_to_mc(const struct status_s* s) {
  return &mincost[s->offset_y + 16][s->offset_x + 16][s->alive_y][s->dead_y][s->alive_x][s->dead_x];
}
int sy = -1, sx = -1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

int H, W;
char S[16][16];

int gomi_cnt[16][16];

/* [offset_y][offset_x][alive_y][dead_y][alive_x][dead_x] */
int mincost[32][32][16][16][16][16];

struct status_s {
	int offset_y, offset_x, alive_y, dead_y, alive_x, dead_x;
};

int* status_to_mc(const struct status_s* s) {
	return &mincost[s->offset_y + 16][s->offset_x + 16][s->alive_y][s->dead_y][s->alive_x][s->dead_x];
}

int sy = -1, sx = -1;

/* 指定の方向にゴミを移動した後の状態を求める */
struct status_s next_status(const struct status_s* s, int dy, int dx) {
	struct status_s res = *s;
	res.offset_y += dy;
	res.offset_x += dx;
	if (res.alive_y < -res.offset_y) res.alive_y = -res.offset_y;
	if (H - res.offset_y < res.dead_y) res.dead_y = H - res.offset_y;
	if (res.alive_x < -res.offset_x) res.alive_x = -res.offset_x;
	if (W - res.offset_x < res.dead_x) res.dead_x = W - res.offset_x;
	return res;
}

/* 指定の状態で高橋君が汚れていないかを求める */
int is_ok(const struct status_s* s) {
	int ty = sy - s->offset_y, tx = sx - s->offset_x;
	if (ty < s->alive_y || s->dead_y <= ty || tx < s->alive_x || s->dead_x <= tx) return 1;
	return S[ty][tx] != '#';
}

/* 指定の状態ですべてのゴミが消滅したかを求める */
int is_goal(const struct status_s* s) {
	if (s->alive_y >= s->dead_y || s->alive_x >= s->dead_x) return 1;
	return (
		gomi_cnt[s->dead_y][s->dead_x] -
		gomi_cnt[s->dead_y][s->alive_x] -
		gomi_cnt[s->alive_y][s->dead_x] +
		gomi_cnt[s->alive_y][s->alive_x]
	) == 0;
}

struct status_s q[sizeof(mincost) / sizeof(int)];

int main(void) {
	int i, j;
	int qs = 0, qe = 1;
	if (scanf("%d%d", &H, &W) != 2) return 1;
	for (i = 0; i < H; i++) {
		if (scanf("%15s", S[i]) != 1) return 1;
		for (j = 0; j < W; j++) {
			if (S[i][j] == '#') gomi_cnt[i + 1][j + 1] = 1;
			if (S[i][j] == 'T') {
				sy = i;
				sx = j;
			}
		}
	}
	if (sy < 0) {
		puts("takahasi-kun not found!");
		return 42;
	}
	for (i = 1; i <= H; i++) {
		for (j = 1; j <= W; j++) gomi_cnt[i][j] += gomi_cnt[i][j - 1];
		for (j = 1; j <= W; j++) gomi_cnt[i][j] += gomi_cnt[i - 1][j];
	}
	memset(mincost, 0x7f, sizeof(mincost));
	q[0] = (struct status_s){ 0, 0, 0, H, 0, W };
	*status_to_mc(&q[0]) = 0;
	while (qs < qe) {
		struct status_s cur = q[qs++];
		int curcost = *status_to_mc(&cur);
		if (is_goal(&cur)) {
			printf("%d\n", curcost);
			return 0;
		}
		for (i = 0; i < 4; i++) {
			int dy = i < 2 ? (i & 1) * 2 - 1 : 0;
			int dx = i < 2 ? 0 : (i & 1) * 2 - 1;
			struct status_s next = next_status(&cur, dy, dx);
			if (is_ok(&next)) {
				int *nextcost = status_to_mc(&next);
				if (*nextcost > curcost + 1) {
					*nextcost = curcost + 1;
					q[qe++] = next;
				}
			}
		}
	}
	puts("-1");
	return 0;
}

Submission Info

Judge Result