結果

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

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
01.txt AC 4 ms
3,020 KB
02.txt AC 4 ms
3,044 KB
03.txt AC 0 ms
3,368 KB
04.txt AC 4 ms
3,072 KB
05.txt AC 40 ms
4,032 KB
06.txt AC 44 ms
4,044 KB
07.txt AC 8 ms
4,072 KB
08.txt AC 96 ms
3,836 KB
09.txt AC 120 ms
3,976 KB
10.txt AC 324 ms
8,264 KB
11.txt AC 44 ms
4,088 KB
12.txt AC 72 ms
3,976 KB
99_system_test1.txt AC 8 ms
4,036 KB
challenge01.txt AC 1,048 ms
8,232 KB
system_test1.txt AC 704 ms
8,228 KB
system_test2.txt AC 4 ms
3,328 KB
system_test3.txt AC 44 ms
4,056 KB
system_test4.txt AC 0 ms
3,332 KB
system_test5.txt AC 4 ms
3,664 KB
system_test6.txt AC 232 ms
8,284 KB
system_test7.txt AC 364 ms
8,228 KB
system_test8.txt AC 8 ms
3,396 KB
system_test9.txt AC 8 ms
4,032 KB
system_test10.txt AC 4 ms
3,332 KB
system_test11.txt AC 484 ms
8,328 KB
system_test12.txt AC 28 ms
4,020 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; }
    @safe pure bool inGrid() { return 0 <= r && r < h && 0 <= c && c < w; }
    @safe pure int p2i() { return cast(int)w*r+c; }

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

    @safe pure auto around4()
    {
      return [Pos(r-1, c), Pos(r, c+1), Pos(r+1, c), Pos(r, c-1)]
        .filter!(p => p.inGrid);
    }
    @safe 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);
    }
  }

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

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

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

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

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

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

@safe auto grid(T)(size_t h, size_t w)
{ return Grid!(h, w).Data!T(new T[][](h, w)); }
@safe 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