Submission #68991886

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 A[512][512];
int mincost[512][512][2];
struct status_s {
  int y, x, toggled;
} q[512 * 512 * 2];
int main(void) {
  int i, j;
  int sy = -1, sx = -1, gy = -1, gx = -1;
  int qs = 0, qe = 0;
  int ans, candidate;
  if (scanf("%d%d", &H, &W) != 2) return 1;
  for (i = 0; i < H; i++) {
    if (scanf("%511s", A[i]) != 1) return 1;
    for (j = 0; j < W; j++) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

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

int mincost[512][512][2];

struct status_s {
	int y, x, toggled;
} q[512 * 512 * 2];

int main(void) {
	int i, j;
	int sy = -1, sx = -1, gy = -1, gx = -1;
	int qs = 0, qe = 0;
	int ans, candidate;
	if (scanf("%d%d", &H, &W) != 2) 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 (sy < 0 || gy < 0) {
		puts("ERROR");
		return 42;
	}
	memset(mincost, 0x7f, sizeof(mincost));
	mincost[sy][sx][0] = 0;
	q[qe++] = (struct status_s){ sy, sx, 0 };
	while (qs < qe) {
		struct status_s cur = q[qs++];
		for (i = 0; i < 4; i++) {
			int d = (i & 1) * 2 - 1;
			int dy = i & 2 ? d : 0, dx = i & 2 ? 0 : d;
			int ny = cur.y + dy, nx = cur.x + dx;
			if (
				0 <= ny && ny < H && 0 <= nx && nx < W &&
				A[ny][nx] != '#' && A[ny][nx] != "xo"[cur.toggled]
			) {
				int nt = cur.toggled ^ (A[ny][nx] == '?');
				int nc = mincost[cur.y][cur.x][cur.toggled] + 1;
				if (mincost[ny][nx][nt] > nc) {
					mincost[ny][nx][nt] = nc;
					q[qe++] = (struct status_s){ ny, nx, nt };
				}
			}
		}
	}
	ans = mincost[gy][gx][0];
	candidate = mincost[gy][gx][1];
	if (candidate < ans) ans = candidate;
	printf("%d\n", ans < H * W * 2 ? ans : -1);
	return 0;
}

Submission Info

Judge Result