結果

問題 No.124 門松列(3)
コンテスト
ユーザー mayoko_
提出日時 2015-01-11 23:51:20
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
MLE  
実行時間 -
コード長 2,184 bytes
コンパイル時間 2,782 ms
コンパイル使用メモリ 78,320 KB
実行使用メモリ 814,620 KB
最終ジャッジ日時 2024-06-22 03:58:06
合計ジャッジ時間 13,707 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other MLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

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][12][MAXH][MAXW];

struct state{
    int before2;
    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++) {
                for (int l = 0; l < 12; l++) {
                    d[k][l][i][j] = INF;
                }
            }
        }
    }
    d[0][0][0][0] = 0;
    queue<state> que;
    state s; s.before2 = 0; 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 (now.cost+1 > d[now.before][M[now.y][now.x]][ny][nx]) continue;
            d[now.before][M[now.y][now.x]][ny][nx] = now.cost + 1;
            state next;
            next.before2 = now.before;
            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++) {
        for (int j = 0; j < 12; j++) {
            ans = min(ans, d[i][j][H-1][W-1]);
        }
    }
    if (ans == INF) ans = -1;
    cout << ans << endl;
    return 0;
}
0