結果

問題 No.124 門松列(3)
ユーザー bal4ubal4u
提出日時 2019-09-25 19:56:36
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 27 ms / 5,000 ms
コード長 1,262 bytes
コンパイル時間 1,627 ms
コンパイル使用メモリ 31,520 KB
実行使用メモリ 26,524 KB
最終ジャッジ日時 2023-10-23 20:15:54
合計ジャッジ時間 2,833 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,372 KB
testcase_01 AC 1 ms
4,372 KB
testcase_02 AC 1 ms
4,372 KB
testcase_03 AC 27 ms
26,524 KB
testcase_04 AC 1 ms
4,372 KB
testcase_05 AC 1 ms
4,372 KB
testcase_06 AC 1 ms
4,372 KB
testcase_07 AC 0 ms
4,372 KB
testcase_08 AC 1 ms
4,372 KB
testcase_09 AC 1 ms
4,372 KB
testcase_10 AC 1 ms
4,372 KB
testcase_11 AC 1 ms
4,372 KB
testcase_12 AC 1 ms
4,372 KB
testcase_13 AC 1 ms
4,372 KB
testcase_14 AC 1 ms
4,372 KB
testcase_15 AC 1 ms
4,372 KB
testcase_16 AC 3 ms
4,372 KB
testcase_17 AC 1 ms
4,372 KB
testcase_18 AC 1 ms
4,372 KB
testcase_19 AC 2 ms
4,372 KB
testcase_20 AC 2 ms
4,372 KB
testcase_21 AC 1 ms
4,372 KB
testcase_22 AC 2 ms
4,372 KB
testcase_23 AC 1 ms
4,372 KB
testcase_24 AC 1 ms
4,372 KB
testcase_25 AC 1 ms
4,372 KB
testcase_26 AC 1 ms
4,372 KB
testcase_27 AC 1 ms
4,372 KB
testcase_28 AC 1 ms
4,372 KB
testcase_29 AC 2 ms
4,372 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// yukicoder: No.124 門松列(3)
// 2019.9.25 bal4u

#include <stdio.h>

#if 1
int getchar_unlocked(void);
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif
int in()
{
	int n = 0, c = gc();
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

typedef struct { int r, c, r1, c1, s; } Q;
Q q[10005]; int top, end;
int W, H;
char m[105][105];
int mv[4][2] = {{-1,0}, {0,1}, {1,0}, {0,-1}};
char vis[105][105][105][105];

int check(int a, int b, int c) {
	if (a == b || a == c || b == c) return 0;
	if (a > b && b < c) return 1;
	if (a < b && b > c) return 1;
	return 0;
}

int bfs() {
	int i, r, c; Q a;
	
	top = 0, end = 1;
	while (top != end) {
		a = q[top++];
		if (a.r == H-1 && a.c == W-1) return a.s;
		if (vis[a.r][a.c][a.r1][a.c1]) continue;
		vis[a.r][a.c][a.r1][a.c1] = 1;
		for (i = 0; i < 4; i++) {
			r = a.r+mv[i][0], c = a.c+mv[i][1];
			if (r < 0 || r >= H || c < 0 || c >= W) continue;
			if (a.s < 1 || check(m[r][c], m[a.r][a.c], m[a.r1][a.c1])) {
				q[end].r = r, q[end].c = c;
				q[end].r1 = a.r, q[end].c1 = a.c, q[end++].s = a.s+1;
			}
		}
	}
	return -1;
}

int main()
{
	int r, c;

	W = in(), H = in();
	for (r = 0; r < H; r++) for (c = 0; c < W; c++) m[r][c] = in();
	printf("%d\n", bfs());
	return 0;
}
0