結果

問題 No.124 門松列(3)
ユーザー koba-e964koba-e964
提出日時 2015-06-23 16:39:19
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,406 bytes
コンパイル時間 603 ms
コンパイル使用メモリ 67,812 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-07 17:10:57
合計ジャッジ時間 1,530 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 4 ms
5,376 KB
testcase_04 AC 4 ms
5,376 KB
testcase_05 AC 4 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 1 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 1 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 3 ms
5,376 KB
testcase_24 AC 3 ms
5,376 KB
testcase_25 AC 3 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 3 ms
5,376 KB
testcase_29 AC 4 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <queue>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef pair<int, int> PI;

const int K = 11;
const int N = 101;
const int inf = 100000;
int m[N][N];
int dp[K][N][N];
struct dat {
  int p0, p1, cur;
  PI pos;
  int dist;
};

bool is_kado(int x, int y, int z) {
  if (x != y && y != z && z != x) {
    return !((x < y && y < z) || (x > y && y > z));
  }
  return 0;
}
int main(void){
  int w, h;
  cin >> w >> h;
  REP(i, 0, h) {
    REP(j, 0, w) {
      cin >> m[i][j];
      REP(k, 0, K) {
	dp[k][i][j] = inf;
      }
    }
  }
  queue<dat> que;
  que.push((dat) {-1, -1, m[0][0], PI(0,0), 0});
  while (! que.empty()) {
    dat p = que.front(); que.pop();
    if (p.p0 != -1 && p.p1 != -1 && ! is_kado(p.p0, p.p1, p.cur)) {
      continue;
    }
    int x = p.pos.first;
    int y = p.pos.second;
    if (p.p1 >= 0 && p.dist >= dp[p.p1][x][y]) {
      continue;
    }
    if (p.p1 >= 0) {
      dp[p.p1][x][y] = p.dist;
    }
    int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
    REP(i, 0, 4) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if (nx < 0 || nx >= h || ny < 0 || ny >= w) {
	continue;
      }
      que.push((dat) {p.p1, p.cur, m[nx][ny], PI(nx, ny), p.dist + 1});
    }
  }
  int mi = inf;
  REP(i, 0, K) {
    mi = min(mi, dp[i][h - 1][w - 1]);
  }
  cout << (mi == inf ? -1 : mi) << endl;
}
0