Submission #57896546

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 <stdlib.h>
#define MOD_BY 49130563
#define FACTOR 48195181LL
#define FACTOR2 (FACTOR * FACTOR % MOD_BY)
struct yx_t {
  int y, x;
};
struct hashtable_data {
  int key_y, key_x, key_d;
  struct yx_t value;
  struct hashtable_data* next;
};
struct hashtable_data* hashtable[MOD_BY];
struct yx_t* get_hashtable(int y, int x, int d) {
  int hash = (int)((y * FACTOR2 + x * FACTOR + d) % MOD_BY);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

#define MOD_BY 49130563
#define FACTOR 48195181LL
#define FACTOR2 (FACTOR * FACTOR % MOD_BY)

struct yx_t {
	int y, x;
};

struct hashtable_data {
	int key_y, key_x, key_d;
	struct yx_t value;
	struct hashtable_data* next;
};

struct hashtable_data* hashtable[MOD_BY];

struct yx_t* get_hashtable(int y, int x, int d) {
	int hash = (int)((y * FACTOR2 + x * FACTOR + d) % MOD_BY);
	struct hashtable_data** p = &hashtable[hash];
	while (*p != NULL) {
		if ((*p)->key_y == y && (*p)->key_x == x && (*p)->key_d == d) return &(*p)->value;
		p = &(*p)->next;
	}
	*p = malloc(sizeof(**p));
	if (*p == NULL) exit(2);
	**p = (struct hashtable_data){ y, x, d, {-1, -1}, NULL };
	return &(*p)->value;
}

const int dyx[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; /* {dy, dx} */

int H, W;

struct yx_t get_next_kabe(int y, int x, int d) {
	if (y < 1 || H < y || x < 1 || W < x) {
		/* 盤外 */
		return (struct yx_t){ y, x };
	} else {
		struct yx_t* hd = get_hashtable(y, x, d);
		if (hd->y < 0 && hd->x < 0) {
			/* 壁がある */
			return (struct yx_t){ y, x };
		} else {
			/* 壁が無い → 探索を続行し、縮約 */
			struct yx_t res = get_next_kabe(y + dyx[d][0], x + dyx[d][1], d);
			*hd = res;
			return res;
		}
	}
}

int main(void) {
	int Q;
	int i, j;
	int ans;
	if (scanf("%d%d%d", &H, &W, &Q) != 3) return 1;
	ans = H * W;
	for (i = 0; i < Q; i++) {
		int R, C;
		struct yx_t* hd;
		if (scanf("%d%d", &R, &C) != 2) return 1;
		hd = get_hashtable(R, C, 0);
		if (hd->y < 0 && hd->x < 0) {
			/* 壁がある (破壊されていない) */
			ans--;
			for (j = 0; j < 4; j++) {
				*get_hashtable(R, C, j) = get_next_kabe(R + dyx[j][0], C + dyx[j][1], j);
			}
		} else {
			/* 壁が無い (破壊されている) */
			for (j = 0; j < 4; j++) {
				struct yx_t pos = get_next_kabe(R, C, j);
				if (1 <= pos.y && pos.y <= H && 1 <= pos.x && pos.x <= W) {
					/* 見た先に壁がある */
					int k;
					ans--;
					for (k = 0; k < 4; k++) {
						*get_hashtable(pos.y, pos.x, k) = get_next_kabe(pos.y + dyx[k][0], pos.x + dyx[k][1], k);
					}
				}
			}
		}
	}
	printf("%d\n", ans);
}

/*

各マスについて、それぞれの方向に見て最初に現れる壁の位置をハッシュテーブル (連想配列) で管理
Union-Find的に縮約する

*/

Submission Info

Judge Result