結果

問題 No.124 門松列(3)
コンテスト
ユーザー bal4u
提出日時 2019-09-25 19:54:33
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,262 bytes
コンパイル時間 468 ms
コンパイル使用メモリ 31,744 KB
実行使用メモリ 26,496 KB
最終ジャッジ日時 2024-09-22 13:51:24
合計ジャッジ時間 1,355 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20 WA * 6
権限があれば一括ダウンロードができます

ソースコード

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 < W; r++) for (c = 0; c < W; c++) m[r][c] = in();
	printf("%d\n", bfs());
	return 0;
}
0