結果

問題 No.340 雪の足跡
ユーザー te-shte-sh
提出日時 2017-07-07 11:41:55
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 684 ms / 1,000 ms
コード長 1,868 bytes
コンパイル時間 843 ms
コンパイル使用メモリ 107,404 KB
実行使用メモリ 35,316 KB
最終ジャッジ日時 2024-06-12 20:45:31
合計ジャッジ時間 8,581 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 1 ms
6,944 KB
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,944 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 3 ms
6,944 KB
testcase_13 AC 4 ms
6,944 KB
testcase_14 AC 50 ms
11,700 KB
testcase_15 AC 54 ms
11,832 KB
testcase_16 AC 26 ms
6,948 KB
testcase_17 AC 61 ms
12,160 KB
testcase_18 AC 58 ms
12,028 KB
testcase_19 AC 62 ms
13,236 KB
testcase_20 AC 162 ms
34,676 KB
testcase_21 AC 54 ms
6,948 KB
testcase_22 AC 12 ms
27,788 KB
testcase_23 AC 442 ms
32,996 KB
testcase_24 AC 80 ms
31,856 KB
testcase_25 AC 119 ms
35,008 KB
testcase_26 AC 21 ms
6,940 KB
testcase_27 AC 4 ms
6,940 KB
testcase_28 AC 36 ms
6,940 KB
testcase_29 AC 413 ms
24,512 KB
testcase_30 AC 317 ms
22,516 KB
testcase_31 AC 601 ms
31,332 KB
testcase_32 AC 684 ms
35,316 KB
testcase_33 AC 661 ms
34,140 KB
testcase_34 AC 676 ms
34,232 KB
testcase_35 AC 644 ms
33,860 KB
testcase_36 AC 653 ms
32,992 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.chomp.splitter(' ');
    auto pr = b.front.to!size_t; b.popFront();
    foreach (i; 0..m) {
      auto s = pr, t = b.front.to!size_t; b.popFront(), pr = t;
      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 = Queue!Qitem(wh), visited = new bool[](wh);
  q.insertBack(Qitem(0, 0));
  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..");
}

struct Queue(T)
{
  T[] buf;
  size_t s, t;

  this(size_t n) { buf = new T[](n); }
  auto empty() { return s == t; }
  auto front() { return buf[s]; }
  auto removeFront() { ++s; }
  auto insertBack(T v) { buf[t++] = v; }
}
0