Submission #67781143

---

Source Code Expand

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

#define MOD_BY 15010529
#define MULT 8477633

int hash(int r, int c) {
	int res = (int)(((long long)r * MULT + c) % MOD_BY);
	if (res < 0) res += MOD_BY;
	return res;
}

struct data_s {
	int r, c;
	int visited;
	struct data_s* next;
};

struct data_s* table[MOD_BY];

int* get_visited(int r, int c, int create) {
	int h = hash(r, c);
	struct data_s** p = &table[h];
	while (*p != NULL) {
		if ((*p)->r == r && (*p)->c == c) {
			return &(*p)->visited;
		}
		p = &(*p)->next;
	}
	if (create) {
		*p = malloc(sizeof(**p));
		if (*p == NULL) exit(2);
		(*p)->r = r;
		(*p)->c = c;
		(*p)->visited = 0;
		(*p)->next = NULL;
		return &(*p)->visited;
	} else {
		return NULL;
	}
}

int H, W, K;
int r[212345], c[212345];

struct queue_s {
	int r, c;
} q[212345 * 10];

int main(void) {
	int i, j;
	int qs = 0, qe = 0;
	if (scanf("%d%d%d", &H, &W, &K) != 3) return 1;
	for (i = 0; i < K; i++) {
		if (scanf("%d%d", &r[i], &c[i]) != 2) return 1;
		get_visited(r[i], c[i], 1);
	}
	for (i = 1; i <= W; i++) {
		if (i != 1) get_visited(0, i, 1);
		if (i != W) get_visited(H + 1, i, 1);
	}
	for (i = 1; i <= H; i++) {
		if (i != 1) get_visited(i, 0, 1);
		if (i != H) get_visited(i, W + 1, 1);
	}
	*get_visited(0, W + 1, 1) = 1;
	get_visited(H + 1, 0, 1);

	q[qe++] = (struct queue_s){ 0, W + 1 };
	while (qs < qe) {
		struct queue_s cur = q[qs++];
		for (i = -1; i <= 1; i++) {
			for (j = -1; j <= 1; j++) {
				int nr = cur.r + i, nc = cur.c + j;
				int *v = get_visited(nr, nc, 0);
				if (v != NULL && !*v) {
					*v = 1;
					q[qe++] = (struct queue_s){ nr, nc };
				}
			}
		}
	}

	puts(*get_visited(H + 1, 0, 1) ? "No" : "Yes");
	return 0;
}

/*

壁の上を8方向に移動して、右上→左下に行ける→No, 行けない→Yes
入力の障害物に加え、外周((1,1)と(H,W)の4方向周囲は除く)が使える

*/

Submission Info

Judge Result