結果

問題 No.124 門松列(3)
コンテスト
ユーザー mayoko_
提出日時 2015-01-12 14:10:22
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 1,947 bytes
コンパイル時間 649 ms
コンパイル使用メモリ 78,152 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-22 04:32:07
合計ジャッジ時間 1,341 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>

#define INF 1000000000

using namespace std;
typedef long long ll;

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

const int MAXH = 110;
const int MAXW = 110;
int M[MAXH][MAXW];
int d[12][MAXH][MAXW];

struct state{
    int before;
    int cost;
    int y;
    int x;
};

bool isKM(int a, int b, int c) {
    if (a == 0 || b == 0 || c == 0) return true;
    if (a == b || b == c || c == a) return false;
    if (b < a && b < c) return true;
    if (b > a && b > c) return true;
    return false;
}

int main(void) {
    int W, H;
    cin >> W >> H;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> M[i][j];
            for (int k = 0; k < 12; k++) {
                d[k][i][j] = INF;
            }
        }
    }
    d[0][0][0] = 0;
    queue<state> que;
    state s; s.before = 0; s.cost = 0; s.y = 0; s.x = 0;
    que.push(s);
    while (!que.empty()) {
        state now = que.front(); que.pop();
        for (int k = 0; k < 4; k++) {
            int nx = now.x + dx[k];
            int ny = now.y + dy[k];
            if (nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
            if (!isKM(now.before, M[now.y][now.x], M[ny][nx])) continue;
            if (d[M[now.y][now.x]][ny][nx] < INF) continue;
            d[M[now.y][now.x]][ny][nx] = now.cost + 1;
            state next;
            next.before = M[now.y][now.x];
            next.cost = now.cost + 1;
            next.y = ny;
            next.x = nx;
            que.push(next);
        }
    }
    int ans = INF;
    for (int i = 0; i < 12; i++) {
        ans = min(ans, d[i][H-1][W-1]);
    }
    if (ans == INF) ans = -1;
    cout << ans << endl;
    return 0;
}
0