(cache)Submission #76788349 - AtCoder Beginner Contest 453

Contest Duration: 2026-04-11(Sat) 21:00 - 2026-04-11(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #76788349

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <string.h>
int H, W;
char S[1024][1024];
const int dyx[4][2] = {{ 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 }};
int dir[1024][1024][4];
int came_dir[1024][1024][4];
int qs = 0, qe = 0;
struct status_s {
  int y, x, dir; /* o, x の場合のみ dir を管理する */
} q[1024 * 1024 * 4];
char ans[1024 * 1024 * 4];
int main(void) {
  int i, j;
  int sy = -1, sx = -1, gy = -1, gx = -1;
  if (scanf("%d%d", &H, &W) != 2) return 1;
  for (i = 0; i < H; i++) {
    if (scanf("%1023s", S[i]) != 1) return 1;
    for (j = 0; j < W; j++) {
      if (S[i][j] == 'S') { sy = i; sx = j; }
      if (S[i][j] == 'G') { gy = i; gx = j; }
    }
  }
  if (sy < 0 || gy < 0) {
    puts("f*ck");
    return 42;
  }
  memset(dir, -1, sizeof(dir));
  dir[sy][sx][0] = 72;
  q[qe++] = (struct status_s){ sy, sx, 0 };
  while (qs < qe) {
    struct status_s cur = q[qs++];
    for (i = 0; i < 4; i++) {
      int ny = cur.y + dyx[i][0], nx = cur.x + dyx[i][1];
      if (
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

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

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

int dir[1024][1024][4];
int came_dir[1024][1024][4];

int qs = 0, qe = 0;
struct status_s {
	int y, x, dir; /* o, x の場合のみ dir を管理する */
} q[1024 * 1024 * 4];

char ans[1024 * 1024 * 4];

int main(void) {
	int i, j;
	int sy = -1, sx = -1, gy = -1, gx = -1;
	if (scanf("%d%d", &H, &W) != 2) return 1;
	for (i = 0; i < H; i++) {
		if (scanf("%1023s", S[i]) != 1) return 1;
		for (j = 0; j < W; j++) {
			if (S[i][j] == 'S') { sy = i; sx = j; }
			if (S[i][j] == 'G') { gy = i; gx = j; }
		}
	}
	if (sy < 0 || gy < 0) {
		puts("f*ck");
		return 42;
	}
	memset(dir, -1, sizeof(dir));
	dir[sy][sx][0] = 72;
	q[qe++] = (struct status_s){ sy, sx, 0 };
	while (qs < qe) {
		struct status_s cur = q[qs++];
		for (i = 0; i < 4; i++) {
			int ny = cur.y + dyx[i][0], nx = cur.x + dyx[i][1];
			if (
				0 <= ny && ny < H && 0 <= nx && nx < W &&
				S[ny][nx] != '#' &&
				(S[cur.y][cur.x] != 'o' || cur.dir == i) &&
				(S[cur.y][cur.x] != 'x' || cur.dir != i)
			) {
				int ndir = S[ny][nx] == 'o' || S[ny][nx] == 'x' ? i : 0;
				if (dir[ny][nx][ndir] < 0) {
					dir[ny][nx][ndir] = i;
					came_dir[ny][nx][ndir] = cur.dir;
					q[qe++] = (struct status_s){ ny, nx, ndir };
				}
			}
		}
	}
	if (dir[gy][gx][0] < 0) {
		puts("No");
	} else {
		char *pans = ans + sizeof(ans) - 1;
		int y = gy, x = gx, d = 0;
		while (dir[y][x][d] < 4) {
			int cur_dir = dir[y][x][d];
			int next_dir = came_dir[y][x][d];
			if (cur_dir < 0) {
				printf("ERROR!!!!! dir[%d][%d][%d] = %d\n", y, x, d, cur_dir);
				return 72;
			}
			*(--pans) = "RLDU"[cur_dir];
			y -= dyx[cur_dir][0];
			x -= dyx[cur_dir][1];
			d = next_dir;
		}
		puts("Yes");
		puts(pans);
	}
	return 0;
}

Submission Info

Submission Time	2026-06-20 08:44:05
Task	D - Go Straight
User	mikecat
Language	C23 (GCC 14.2.0)
Score	425
Code Size	1892 Byte
Status	AC
Exec Time	209 ms
Memory	84648 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

425 / 425

Status

× 3

× 46

Set Name	Test Cases
Sample	example_00.txt, example_01.txt, example_02.txt
All	example_00.txt, example_01.txt, example_02.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt

Case Name	Status	Exec Time	Memory
example_00.txt	AC	7 ms	17996 KiB
example_01.txt	AC	7 ms	17964 KiB
example_02.txt	AC	7 ms	17836 KiB
hand_00.txt	AC	61 ms	46652 KiB
hand_01.txt	AC	11 ms	22956 KiB
hand_02.txt	AC	203 ms	84648 KiB
hand_03.txt	AC	209 ms	84648 KiB
hand_04.txt	AC	7 ms	18024 KiB
hand_05.txt	AC	61 ms	46636 KiB
hand_06.txt	AC	50 ms	59396 KiB
hand_07.txt	AC	59 ms	46724 KiB
hand_08.txt	AC	10 ms	18860 KiB
hand_09.txt	AC	7 ms	17852 KiB
random_00.txt	AC	10 ms	19048 KiB
random_01.txt	AC	99 ms	51660 KiB
random_02.txt	AC	92 ms	49852 KiB
random_03.txt	AC	10 ms	18876 KiB
random_04.txt	AC	97 ms	51664 KiB
random_05.txt	AC	70 ms	45100 KiB
random_06.txt	AC	10 ms	19032 KiB
random_07.txt	AC	10 ms	18948 KiB
random_08.txt	AC	78 ms	47320 KiB
random_09.txt	AC	82 ms	48004 KiB
random_10.txt	AC	75 ms	45612 KiB
random_11.txt	AC	83 ms	47108 KiB
random_12.txt	AC	82 ms	47928 KiB
random_13.txt	AC	9 ms	19024 KiB
random_14.txt	AC	82 ms	48200 KiB
random_15.txt	AC	15 ms	31116 KiB
random_16.txt	AC	10 ms	19212 KiB
random_17.txt	AC	10 ms	19468 KiB
random_18.txt	AC	10 ms	20548 KiB
random_19.txt	AC	10 ms	20696 KiB
random_20.txt	AC	10 ms	18956 KiB
random_21.txt	AC	23 ms	35288 KiB
random_22.txt	AC	10 ms	19004 KiB
random_23.txt	AC	10 ms	19380 KiB
random_24.txt	AC	21 ms	35528 KiB
random_25.txt	AC	13 ms	25276 KiB
random_26.txt	AC	10 ms	19512 KiB
random_27.txt	AC	78 ms	50748 KiB
random_28.txt	AC	10 ms	19004 KiB
random_29.txt	AC	15 ms	25400 KiB
random_30.txt	AC	45 ms	40648 KiB
random_31.txt	AC	36 ms	39052 KiB
random_32.txt	AC	14 ms	23308 KiB