結果

問題 No.124 門松列(3)
ユーザー tsukio
提出日時 2016-03-17 13:56:49
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 2,060 bytes
コンパイル時間 760 ms
コンパイル使用メモリ 67,588 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-01 08:51:26
合計ジャッジ時間 1,799 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;
struct Point {
    Point(int x, int y, int dir) {
        this->x = x;
        this->y = y;
        this->dir = dir;
    }
    int x;
    int y;
    int dir;
};
bool IsKadomatsuSequence(int prev, int current, int next) {
    if (prev < current && next < current && prev != next)
        return true;
    if (current < prev && current < next && prev != next)
        return true;
    return false;
}
int main() {
    const int INF = INT_MAX;
    const int MAX_WIDTH = 100;
    const int MAX_HEIGHT = 100;
    const int DIR_COUNT = 4;
    int dx[] = { -1, 1, 0, 0 };
    int dy[] = { 0, 0, -1, 1 };
    int w, h;
    cin >> w >> h;
    int board[MAX_WIDTH][MAX_HEIGHT];
    for (int y = 0; y < h; y++) {
        for (int x = 0; x < w; x++) {
            cin >> board[x][y];
        }
    }
    int dist[MAX_WIDTH][MAX_HEIGHT][DIR_COUNT];
    for (int x = 0; x < MAX_WIDTH; x++) {
        for (int y = 0; y < MAX_HEIGHT; y++) {
            for (int dir = 0; dir < DIR_COUNT; dir++) {
                dist[x][y][dir] = INF;
            }
        }
    }
    for (int dir = 0; dir < DIR_COUNT; dir++) {
        dist[0][0][dir] = 0;
    }
    dist[1][0][1] = 1;
    dist[0][1][3] = 1;
    
    queue<Point> points;
    points.push(Point(1, 0, 1));
    points.push(Point(0, 1, 3));
    while (!points.empty()) {
        Point current = points.front(); points.pop();
        int prev_x = current.x - dx[current.dir];
        int prev_y = current.y - dy[current.dir];
        int next_cost = dist[current.x][current.y][current.dir] + 1;
        for (int dir = 0; dir < DIR_COUNT; dir++) {
            int next_x = current.x + dx[dir];
            int next_y = current.y + dy[dir];
            if (next_x < 0 || next_y < 0 || next_x >= w || next_y >= h)
                continue;
            if (!IsKadomatsuSequence(board[prev_x][prev_y], board[current.x][current.y], board[next_x][next_y]))
                continue;
            
            if (next_cost >= dist[next_x][next_y][dir])
                continue;
            dist[next_x][next_y][dir] = next_cost;
            points.push(Point(next_x, next_y, dir));
        }
    }
    int ans = INF;
    for (int dir = 0; dir < DIR_COUNT; dir++) {
        ans = min(ans, dist[w - 1][h - 1][dir]);
    }
    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0