結果

問題 No.340 雪の足跡
ユーザー te-shte-sh
提出日時 2017-07-07 11:15:12
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 937 ms / 1,000 ms
コード長 1,544 bytes
コンパイル時間 913 ms
コンパイル使用メモリ 107,112 KB
実行使用メモリ 54,480 KB
最終ジャッジ日時 2024-06-12 20:44:56
合計ジャッジ時間 11,291 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 3 ms
6,940 KB
testcase_12 AC 4 ms
6,940 KB
testcase_13 AC 6 ms
6,940 KB
testcase_14 AC 64 ms
12,000 KB
testcase_15 AC 68 ms
12,384 KB
testcase_16 AC 37 ms
6,940 KB
testcase_17 AC 81 ms
13,776 KB
testcase_18 AC 77 ms
12,700 KB
testcase_19 AC 80 ms
13,772 KB
testcase_20 AC 257 ms
23,188 KB
testcase_21 AC 106 ms
6,944 KB
testcase_22 AC 9 ms
11,384 KB
testcase_23 AC 626 ms
22,804 KB
testcase_24 AC 156 ms
22,692 KB
testcase_25 AC 213 ms
22,928 KB
testcase_26 AC 38 ms
7,276 KB
testcase_27 AC 8 ms
6,944 KB
testcase_28 AC 57 ms
11,320 KB
testcase_29 AC 615 ms
54,480 KB
testcase_30 AC 443 ms
14,352 KB
testcase_31 AC 820 ms
36,940 KB
testcase_32 AC 912 ms
22,992 KB
testcase_33 AC 861 ms
23,704 KB
testcase_34 AC 937 ms
23,272 KB
testcase_35 AC 843 ms
23,412 KB
testcase_36 AC 837 ms
23,340 KB
権限があれば一括ダウンロードができます

ソースコード

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;

  if (wh == 1) {
    writeln(0);
    return;
  }

  auto hp = new int[][](h, w);
  auto vp = new int[][](w, h);

  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);
      auto sx = s % w, sy = s / w, tx = t % w, ty = t / w;
      if (sy == ty) {
        ++hp[sy][sx];
        --hp[sy][tx];
      } else {
        ++vp[sx][sy];
        --vp[sx][ty];
      }
    }
  }

  foreach (i; 0..h)
    foreach (j; 1..w)
      hp[i][j] += hp[i][j-1];

  foreach (i; 0..w)
    foreach (j; 1..h)
      vp[i][j] += vp[i][j-1];

  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();
    auto u = qi.v, ux = u % w, uy = u / w;

    size_t[] vc;
    if (ux > 0 && hp[uy][ux-1]) vc ~= u - 1;
    if (ux < w-1 && hp[uy][ux]) vc ~= u + 1;
    if (uy > 0 && vp[ux][uy-1]) vc ~= u - w;
    if (uy < h-1 && vp[ux][uy]) vc ~= u + w;

    foreach (v; vc) {
      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