結果

問題 No.340 雪の足跡
ユーザー te-shte-sh
提出日時 2017-07-07 10:19:30
言語 D
(dmd 2.106.1)
結果
WA  
実行時間 -
コード長 1,201 bytes
コンパイル時間 815 ms
コンパイル使用メモリ 107,440 KB
実行使用メモリ 36,740 KB
最終ジャッジ日時 2024-06-12 20:44:44
合計ジャッジ時間 9,357 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
13,760 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 WA -
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 7 ms
6,940 KB
testcase_12 AC 6 ms
6,940 KB
testcase_13 AC 10 ms
6,944 KB
testcase_14 AC 497 ms
32,276 KB
testcase_15 AC 594 ms
32,440 KB
testcase_16 AC 252 ms
17,868 KB
testcase_17 AC 862 ms
36,532 KB
testcase_18 AC 629 ms
36,740 KB
testcase_19 AC 855 ms
36,608 KB
testcase_20 TLE -
testcase_21 -- -
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 #

import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.container; // SList, DList, BinaryHeap

void main()
{
  auto rd = readln.split.to!(size_t[]), w = rd[0], h = rd[1], n = rd[2];
  auto wh = w * h;

  auto g = new bool[size_t][](wh);

  foreach (_; 0..n) {
    auto m = readln.chomp.to!size_t;
    auto b = readln.split.to!(size_t[]);
    foreach (i; 0..m) {
      auto s = b[i], t = b[i+1];
      if (s > t) swap(s, t);
      if (s/w == t/w) {
        foreach (j; s..t) {
          g[j][j+1] = true;
          g[j+1][j] = true;
        }
      } else {
        auto k = s % w;
        s /= w; t /= w;
        foreach (j; s..t) {
          g[j*w+k][(j+1)*w+k] = true;
          g[(j+1)*w+k][j*w+k] = true;
        }
      }
    }
  }

  struct Qitem { size_t v; int len; }
  auto q = DList!Qitem(Qitem(0, 0)), visited = new bool[](wh);
  visited[0] = true;

  while (!q.empty) {
    auto qi = q.front; q.removeFront();
    foreach (v; g[qi.v].byKey) {
      if (v == wh-1) {
        writeln(qi.len + 1);
        return;
      }
      if (!visited[v]) {
        visited[v] = true;
        q.insertBack(Qitem(v, qi.len + 1));
      }
    }
  }

  writeln("Odekakedekinai..");
}
0