結果

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

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0