結果

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

ソースコード

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