結果

問題 No.20 砂漠のオアシス
ユーザー te-sh
提出日時 2020-02-15 03:58:13
言語 D
(dmd 2.089.1)
結果
AC  
実行時間 120 ms
コード長 7,275 Byte
コンパイル時間 3,664 ms
使用メモリ 12,688 KB
最終ジャッジ日時 2020-02-15 03:58:20

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
01.txt AC 8 ms
3,060 KB
02.txt AC 0 ms
3,080 KB
03.txt AC 4 ms
2,964 KB
04.txt AC 8 ms
3,620 KB
05.txt AC 4 ms
3,768 KB
06.txt AC 108 ms
11,864 KB
07.txt AC 116 ms
12,596 KB
08.txt AC 116 ms
12,688 KB
09.txt AC 120 ms
12,528 KB
10.txt AC 116 ms
12,588 KB
99_challenge01.txt AC 4 ms
2,960 KB
99_challenge02.txt AC 4 ms
2,980 KB
system_test1.txt AC 8 ms
3,416 KB
system_test2.txt AC 8 ms
3,552 KB
system_test3.txt AC 12 ms
4,040 KB
system_test4.txt AC 8 ms
3,860 KB
system_test5.txt AC 20 ms
4,284 KB
system_test6.txt AC 20 ms
3,972 KB
system_test7.txt AC 20 ms
4,284 KB
system_test8.txt AC 28 ms
4,452 KB
system_test9.txt AC 4 ms
3,352 KB
テストケース一括ダウンロード

ソースコード

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

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

version(unittest) {} else
void main()
{
  int N, V, Ox, Oy; io.getV(N, V, Ox, Oy); --Ox; --Oy;
  int[][] L; io.getM(N, N, L);

  auto a = grid(L), g = GraphW!int(N*N);
  foreach (p; a.walk)
    foreach (np; p.around4)
      g.addEdge(p.p2i, np.p2i, a[np]);

  auto d1 = g.dijkstra(a.pos(0, 0).p2i).dist;
  if (V - d1[a.pos(N-1, N-1).p2i] > 0) io.put!"{exit: true}"("YES");

  if (Ox >= 0 && Oy >= 0) {
    auto d2 = g.dijkstra(a.pos(Oy, Ox).p2i).dist;
    if ((V - d1[a.pos(Oy, Ox).p2i])*2 - d2[a.pos(N-1, N-1).p2i] > 0) io.put!"{exit: true}"("YES");
  }

  io.put("NO");
}

template Grid(alias h, alias w)
{
  struct Pos
  {
    int r, c;
    this(int r, int c) { this.r = r; this.c = c; }
    bool inGrid() { return 0 <= r && r < h && 0 <= c && c < w; }
    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); }

pure int distManhattan(T)(T p1, T p2) { return abs(p1.r-p2.r) + abs(p1.c-p2.c); }

struct Graph
{
  alias Node = int;
  Node n;
  Node[][] g;
  alias g this;
  this(Node n) { this.n = n; g = new Node[][](n); }
  void addEdge(Node u, Node v) { g[u] ~= v; }
  void addEdgeB(Node u, Node v) { g[u] ~= v; g[v] ~= u; }
}

struct GraphW(W = int, W i = 10^^9)
{
  alias Node = int, Wt = W, inf = i;
  struct Edge { Node src, dst; Wt wt; alias cap = wt; }
  Node n;
  Edge[][] g;
  alias g this;
  this(Node n) { this.n = n; g = new Edge[][](n); }
  void addEdge(Node u, Node v, Wt w) { g[u] ~= Edge(u, v, w); }
  void addEdgeB(Node u, Node v, Wt w) { g[u] ~= Edge(u, v, w); g[v] ~= Edge(v, u, w); }
}

struct GraphM(W = int, W i = 10^^9)
{
  alias Node = int, Wt = W, inf = i;
  Node n;
  Wt[][] g;
  alias g this;
  this(int n) { this.n = n; g = new Wt[][](n, n); }
  static GraphM!(W, i) init(Node n)
  {
    auto g = GraphM!(W, i)(n);
    foreach (i; 0..n) { g[i][] = inf; g[i][i] = 0; }
    return g;
  }
}

struct Dijkstra(Graph)
{
  alias Node = Graph.Node, Wt = Graph.Wt, Edge = Graph.Edge;
  Graph g;
  alias g this;
  Wt[] dist;
  Node[] prev;

  this(Graph g, Node s)
  {
    this.g = g;
    auto sent = n;

    dist = new Wt[](n);
    dist[] = g.inf;
    dist[s] = 0;

    prev = new Node[](n);
    prev[] = sent;

    auto q = heapify!("a.wt>b.wt")(Array!Edge(Edge(sent, s, 0)));
    while (!q.empty) {
      auto e = q.front; q.removeFront();
      if (prev[e.dst] != sent) continue;
      prev[e.dst] = e.src;
      foreach (f; g[e.dst]) {
        auto w = e.wt+f.wt;
        if (dist[f.dst] > w) {
          dist[f.dst] = w;
          q.insert(Edge(f.src, f.dst, w));
        }
      }
    }
  }
}
Dijkstra!Graph dijkstra(Graph, Node)(Graph g, Node s)
{ return Dijkstra!Graph(g, s); }

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