結果

問題 No.340 雪の足跡
ユーザー roiti46roiti46
提出日時 2016-01-29 23:12:28
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,868 bytes
コンパイル時間 1,262 ms
コンパイル使用メモリ 164,204 KB
実行使用メモリ 14,320 KB
最終ジャッジ日時 2024-09-21 18:38:28
合計ジャッジ時間 6,313 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define EACH(i, a) for (auto i: a)
#define ITR(x, a) for (__typeof(a.begin()) x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define endl '\n'

int W, H, N;
int B[1005], X[1005][1005], used[1005][1005];
const int inf = (int)1e7;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int main(void) {
  cin >> W >> H >> N;
  rep(i, N) {
    int M;
    cin >> M;
    rep(j, M + 1) cin >> B[j];
    rep(j, M) {
      if (abs(B[j] - B[j + 1])%W == 0 && B[j] > B[j + 1]) {
        for (int k = B[j + 1]; k < B[j]; k += W) X[k][k + W] = X[k + W][k] = 1;
      }
      else if (abs(B[j] - B[j + 1])%W == 0 && B[j] < B[j + 1]) {
        for (int k = B[j]; k < B[j + 1]; k += W) X[k][k + W] = X[k + W][k] = 1;
      }
      else if (B[j] > B[j + 1]) {
        for (int k = B[j + 1]; k < B[j]; k += 1) X[k][k + 1] = X[k + 1][k] = 1;
      }
      else if (B[j] < B[j + 1]) {
        for (int k = B[j]; k < B[j + 1]; k += 1) X[k][k + 1] = X[k + 1][k] = 1;
      }
    }
  }

  int ans = inf;
  priority_queue<pair<int, int>> que;
  que.push(make_pair(0, 0));
  while (!que.empty()) {
    auto ele = que.top(); que.pop();
    int cost = ele.first;
    if (ele.second == W*H - 1) {
      ans = cost;
      break;
    }
    int x = ele.second%W, y = ele.second/H;

    rep(i, 4) {
      int nx = x + dx[i], ny = y + dy[i];
      if (!(0 <= nx && nx < W && 0 <= ny && ny < H)) continue;
      if (X[H*y + x][H*ny + nx] == 1 && used[ny][nx] == 0) {
        used[ny][nx] = 1;
        que.push(make_pair(cost + 1, H*ny + nx));
      }
    }
  }
  
  if (ans < inf) {
    cout << ans << endl;
  } else {
    cout << "Odekakedekinai.." << endl;
  }

  return 0;
}
0