結果

問題 No.34 砂漠の行商人
ユーザー te-sh
提出日時 2020-02-15 04:14:36
言語 D
(dmd 2.089.1)
結果
AC  
実行時間 1,040 ms
コード長 5,621 Byte
コンパイル時間 2,000 ms
使用メモリ 8,324 KB
最終ジャッジ日時 2020-02-15 04:14:43

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
01.txt AC 0 ms
3,044 KB
02.txt AC 4 ms
3,004 KB
03.txt AC 0 ms
3,348 KB
04.txt AC 4 ms
3,036 KB
05.txt AC 40 ms
3,996 KB
06.txt AC 44 ms
4,080 KB
07.txt AC 8 ms
4,028 KB
08.txt AC 96 ms
3,948 KB
09.txt AC 120 ms
4,080 KB
10.txt AC 324 ms
8,260 KB
11.txt AC 44 ms
4,048 KB
12.txt AC 68 ms
4,068 KB
99_system_test1.txt AC 8 ms
3,936 KB
challenge01.txt AC 1,040 ms
8,304 KB
system_test1.txt AC 700 ms
8,256 KB
system_test2.txt AC 4 ms
3,456 KB
system_test3.txt AC 44 ms
3,920 KB
system_test4.txt AC 4 ms
3,308 KB
system_test5.txt AC 4 ms
3,768 KB
system_test6.txt AC 232 ms
8,324 KB
system_test7.txt AC 372 ms
8,224 KB
system_test8.txt AC 4 ms
3,316 KB
system_test9.txt AC 8 ms
3,996 KB
system_test10.txt AC 4 ms
3,316 KB
system_test11.txt AC 476 ms
8,212 KB
system_test12.txt AC 28 ms
4,032 KB
テストケース一括ダウンロード

ソースコード

diff #
// URL: https://yukicoder.me/problems/no/34

import std.algorithm, std.array, std.container, std.math, std.range, std.typecons, std.string;

version(unittest) {} else
void main()
{
  int N, V, Sx, Sy, Gx, Gy; io.getV(N, V, Sx, Sy, Gx, Gy); --Sx; --Sy; --Gx; --Gy;
  int[][] L; io.getM(N, N, L);

  auto m = grid(L);
  alias Pos = m.Pos;
  auto S = m.pos(Sy, Sx), G = m.pos(Gy, Gx);

  auto v = m.grid!int, inf = 10^^6;
  foreach (p; v.walk) v[p] = inf;
  v[S] = 0;

  struct E { Pos p; int d, h; }
  auto q = DList!E(E(S, 0, 0));
  while (!q.empty) {
    auto e = q.front; q.removeFront();
    foreach (np; e.p.around4) {
      auto nh = e.h+m[np];
      if (nh >= V) continue;
      if (np == G) io.put!"{exit: true}"(e.d+1);
      if (nh < v[np]) {
        v[np] = nh;
        q.insertBack(E(np, e.d+1, nh));
      }
    }
  }
  io.put(-1);
}

template Grid(alias h, alias w)
{
  struct Pos
  {
    int r, c;
    this(int r, int c) { this.r = r; this.c = c; }
    pure bool inGrid() { return 0 <= r && r < h && 0 <= c && c < w; }
    pure int p2i() { return cast(int)w*r+c; }

    pure Pos opBinary(string op)(Pos q) if (op=="+"||op=="-")
    { return mixin("Pos(r"~op~"q.r, c"~op~"q.c)"); }
    Pos opOpAssign(string op)(Pos q) if (op=="+"||op=="-")
    { mixin("r"~op~"=q.r; c"~op~"=q.c;"); return this; }
    pure Pos opBinary(string op, U)(U a) if (op=="*"||op=="/")
    { return mixin("Pos(r"~op~"a, c"~op~"a)"); }
    Pos opOpAssign(string op, U)(U a) if (op=="*"||op=="/")
    { mixin("r"~op~"=a; c"~op~"=a;"); return this; }
    pure int opBinary(string op: "*")(Pos q)
    { return r*q.r+c*q.c; }

    pure auto around4()
    {
      return [Pos(r-1, c), Pos(r, c+1), Pos(r+1, c), Pos(r, c-1)]
        .filter!(p => p.inGrid);
    }
    pure auto around8()
    {
      return [Pos(r-1, c), Pos(r-1, c+1), Pos(r, c+1), Pos(r+1, c+1),
              Pos(r+1, c), Pos(r+1, c-1), Pos(r, c-1), Pos(r-1, c-1)]
        .filter!(p => p.inGrid);
    }
  }

  struct Data(T)
  {
    alias Pos = Grid!(h, w).Pos;

    T[][] data;

    this(T[][] data) { h = data.length; w = data[0].length; this.data = data; }
    pure Data!T dup() { return Data!T(data.map!"a.dup".array); }

    pure Pos pos(int r, int c) { return Pos(r, c); }
    pure Data!U grid(U)() { return Data!U(new U[][](h, w)); }

    pure T opIndex(size_t r, size_t c) { return data[r][c]; }
    pure T opIndex(Pos p) { return data[p.r][p.c]; }
    Data!T opIndexAssign(T v, size_t r, size_t c) { data[r][c] = v; return this; }
    Data!T opIndexAssign(T v, Pos p) { data[p.r][p.c] = v; return this; }
    Data!T opIndexOpAssign(string op)(T v, size_t r, size_t c)
    { mixin("data[r][c]"~op~"=v;"); return this; }
    Data!T opIndexOpAssign(string op)(T v, Pos p)
    { mixin("data[p.r][p.c]"~op~"=v;"); return this; }
    Data!T opIndexUnary(string op)(size_t r, size_t c) if (op=="++"||op=="--")
      { mixin(op~"data[r][c];"); return this; }
    Data!T opIndexUnary(string op)(Pos p) if (op=="++"||op=="--")
      { mixin(op~"data[p.r][p.c];"); return this; }

    auto walk()
    { return WalkRange(this); }

    private struct WalkRange
    {
      int r, c;
      this(Data!T g) { r = 0; c = 0; }
      @property pure Pos front() { return Pos(r, c); }
      void popFront() { if (++c >= w) { c = 0; ++r; } }
      pure bool empty() { return r >= h; }
    }
  }
}

auto grid(T)(size_t h, size_t w)
{ return Grid!(h, w).Data!T(new T[][](h, w)); }
auto grid(T)(T[][] data)
{ auto h = data.length, w = data[0].length; return Grid!(h, w).Data!T(data); }

auto io = IO!()();
import std.stdio;
struct IO(alias IN = stdin, alias OUT = stdout)
{
  import std.conv, std.format, std.meta, std.traits, core.stdc.stdlib;

  auto getV(T...)(ref T v) { foreach (ref w; v) get(w); }
  auto getA(T)(size_t n, ref T v) if (hasAssignableElements!T)
  { v = new T(n); foreach (ref w; v) get(w); }
  auto getC(T...)(size_t n, ref T v)
  if (allSatisfy!(hasAssignableElements, T))
  {
    foreach (ref w; v) w = new typeof(w)(n);
    foreach (i; 0..n) foreach (ref w; v) get(w[i]);
  }
  auto getM(T)(size_t r, size_t c, ref T v)
  if (hasAssignableElements!T && hasAssignableElements!(ElementType!T))
  { v = new T(r); foreach (ref w; v) getA(c, w); }
  template getS(E...)
  {
    auto getS(T)(size_t n, ref T v)
    { v = new T(n); foreach (ref w; v) foreach (e; E) mixin("get(w."~e~");"); }
  }

  const struct PutConf
  {
    bool newline = true, flush, exit;
    string floatFormat = "%.10f", delimiter = " ";
  }

  auto put(alias conf = "{}", T...)(T v)
  { mixin("const PutConf c = "~conf~"; putMain!c(v);"); }
  auto putB(alias conf = "{}", S, T)(bool c, S t, T f)
  { if (c) put!conf(t); else put!conf(f); }
  auto putRaw(T...)(T v) { OUT.write(v); OUT.writeln; }

  private
  {
    dchar[] buf;
    auto sp = (new dchar[](0)).splitter;
    void nextLine() { IN.readln(buf); sp = buf.splitter; }
    auto get(T)(ref T v) { if (sp.empty) nextLine(); v = sp.front.to!T; sp.popFront(); }

    auto putMain(PutConf c, T...)(T v)
    {
      foreach (i, w; v) {
        putOne!c(w);
        if (i < v.length-1) OUT.write(c.delimiter);
      }
      static if (c.newline) OUT.writeln;
      static if (c.flush) OUT.flush();
      static if (c.exit) exit(0);
    }
    auto putOne(PutConf c, T)(T v)
    {
      static if (isInputRange!T && !isSomeString!T) putRange!c(v);
      else if (isFloatingPoint!T) OUT.write(format(c.floatFormat, v));
      else OUT.write(v);
    }
    auto putRange(PutConf c, T)(T v)
    {
      auto w = v;
      while (!w.empty) {
        putOne!c(w.front); w.popFront();
        if (!w.empty) OUT.write(c.delimiter);
      }
    }
  }
}
0