結果

問題 No.340 雪の足跡
ユーザー te-shte-sh
提出日時 2017-07-07 11:41:55
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 726 ms / 1,000 ms
コード長 1,868 bytes
コンパイル時間 773 ms
コンパイル使用メモリ 93,364 KB
実行使用メモリ 34,932 KB
最終ジャッジ日時 2023-09-03 15:02:43
合計ジャッジ時間 8,963 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,384 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,384 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 3 ms
4,380 KB
testcase_12 AC 3 ms
4,380 KB
testcase_13 AC 5 ms
4,384 KB
testcase_14 AC 51 ms
11,556 KB
testcase_15 AC 55 ms
12,388 KB
testcase_16 AC 28 ms
4,376 KB
testcase_17 AC 65 ms
12,664 KB
testcase_18 AC 63 ms
12,584 KB
testcase_19 AC 65 ms
12,608 KB
testcase_20 AC 161 ms
34,928 KB
testcase_21 AC 56 ms
6,720 KB
testcase_22 AC 13 ms
28,512 KB
testcase_23 AC 462 ms
34,476 KB
testcase_24 AC 83 ms
31,896 KB
testcase_25 AC 130 ms
33,732 KB
testcase_26 AC 24 ms
6,456 KB
testcase_27 AC 5 ms
4,380 KB
testcase_28 AC 40 ms
5,660 KB
testcase_29 AC 437 ms
25,504 KB
testcase_30 AC 323 ms
23,340 KB
testcase_31 AC 645 ms
30,312 KB
testcase_32 AC 726 ms
33,560 KB
testcase_33 AC 692 ms
32,420 KB
testcase_34 AC 712 ms
34,664 KB
testcase_35 AC 664 ms
34,932 KB
testcase_36 AC 657 ms
34,400 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