結果
問題 | No.124 門松列(3) |
ユーザー |
![]() |
提出日時 | 2016-02-05 00:34:03 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 1,754 bytes |
コンパイル時間 | 750 ms |
コンパイル使用メモリ | 72,188 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-21 20:33:46 |
合計ジャッジ時間 | 1,941 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <iostream>#include <vector>#include <limits>#include <algorithm>using namespace std;struct State {int x;int y;int previousValue;int steps;State(int x, int y, int previousValue, int steps) :x(x), y(y), previousValue(previousValue), steps(steps) {}};const int dx[] = { 1, -1, 0, 0 };const int dy[] = { 0, 0, 1, -1 };bool isKadomatsuSequence(int a, int b, int c) {if (a < 0 || b < 0 || c < 0) {return true;}if (a != c) {if (a < b && b > c) {return true;}if (a > b && b < c) {return true;}}return false;}int main() {int w, h;cin >> w >> h;vector<vector<int> > m(w, vector<int>(h));for (int y = 0; y < h; ++y) {for (int x = 0; x < w; ++x) {cin >> m[x][y];}}vector<State> states;vector<vector<vector<int> > > shortest(w, vector<vector<int> >(h, vector<int>(4, numeric_limits<int>::max())));states.push_back(State(0, 0, -1, 0));for (int d = 0; d < 4; ++d) {shortest[0][0][d] = states.back().steps;}while (!states.empty()) {State top = states.back();states.pop_back();int topValue = m[top.x][top.y];for (int d = 0; d < 4; ++d) {State next(top.x + dx[d], top.y + dy[d], topValue, top.steps + 1);if (0 <= next.x && next.x < w&& 0 <= next.y && next.y < h&& isKadomatsuSequence(top.previousValue, topValue, m[next.x][next.y])&& shortest[next.x][next.y][d] > next.steps) {shortest[next.x][next.y][d] = next.steps;if (next.x != w - 1 || next.y != h - 1) {states.push_back(next);}}}}int result = numeric_limits<int>::max();for (int d = 0; d < 4; ++d) {result = min(result, shortest[w - 1][h - 1][d]);}cout << (result == numeric_limits<int>::max() ? -1 : result) << endl;return 0;}