Submission #67690083

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>
#include <inttypes.h>
#define INF 0x7f7f7f7f
const int d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int cnt[3123][3123];
int cost[3123][3123];
struct rc_s {
  int r, c;
} q[3123 * 3123];
int main(void) {
  int H, W, K;
  int i, j;
  int qs = 0, qe = 0;
  uint64_t ans = 0;
  memset(cost, 0x7f, sizeof(cost));
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

#define INF 0x7f7f7f7f

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

int cnt[3123][3123];
int cost[3123][3123];

struct rc_s {
	int r, c;
} q[3123 * 3123];

int main(void) {
	int H, W, K;
	int i, j;
	int qs = 0, qe = 0;
	uint64_t ans = 0;
	memset(cost, 0x7f, sizeof(cost));
	if (scanf("%d%d%d", &H, &W, &K) != 3) return 1;
	for (i = 0; i < K; i++) {
		int R, C;
		if (scanf("%d%d", &R, &C) != 2) return 1;
		cnt[R][C] = 4;
		cost[R][C] = 0;
		q[qe++] = (struct rc_s){ R, C };
	}
	while (qs < qe) {
		struct rc_s cur = q[qs++];
		for (i = 0; i < 4; i++) {
			int nr = cur.r + d[i][0], nc = cur.c + d[i][1];
			/* 1 <= R_i, 1 <= C_i なので、範囲外チェック不要 (外周が番兵になる) */
			/* 外周は盤内と高々1個しか隣接しないので、こちらも考慮不要 */
			if (++cnt[nr][nc] == 2) {
				int best = INF, best2 = INF;
				for (j = 0; j < 4; j++) {
					int r2 = nr + d[j][0], c2 = nc + d[j][1];
					int hoge = cost[r2][c2];
					if (hoge < best) {
						best2 = best;
						best = hoge;
					} else if (hoge < best2) {
						best2 = hoge;
					}
				}
				cost[nr][nc] = best2 + 1;
				q[qe++] = (struct rc_s){ nr, nc };
			}
		}
	}
	for (i = 1; i <= H; i++) {
		for (j = 1; j <= W; j++) {
			if (cost[i][j] < INF) ans += cost[i][j];
		}
	}
	printf("%" PRIu64 "\n", ans);
	return 0;
}

/*

要は、移動を1方向ブロックできる

ゴールに行けるところの周囲をチェックする
周囲2箇所からゴールに行ける → そこもゴールに行ける
そのときのコストは、周囲のコストの小さくない方 + 1

2箇所できたとき、それ以降にもっと有利な(低コストで行ける)条件は出てこない
ベストのところをブロックするしかない
→まずゴールをキューに入れ、順に処理すればおｋ

*/

Submission Info

Judge Result