結果

問題 No.340 雪の足跡
コンテスト
ユーザー te-sh
提出日時 2017-07-07 11:41:55
言語 D
(dmd 2.109.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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