結果

問題 No.659 徘徊迷路
コンテスト
ユーザー te-sh
提出日時 2018-04-16 17:49:29
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 119 ms / 2,000 ms
コード長 2,892 bytes
コンパイル時間 2,583 ms
コンパイル使用メモリ 152,960 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-13 00:30:03
合計ジャッジ時間 4,040 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;

void readV(T...)(ref T t){auto r=readln.splitter;foreach(ref v;t){v=r.front.to!(typeof(v));r.popFront;}}
void readC(T...)(size_t n,ref T t){foreach(ref v;t)v=new typeof(v)(n);foreach(i;0..n){auto r=readln.splitter;foreach(ref v;t){v[i]=r.front.to!(ElementType!(typeof(v)));r.popFront;}}}

void main()
{
  int r, c, t; readV(r, c, t);
  int sx, sy; readV(sx, sy);
  int gx, gy; readV(gx, gy);
  string[] b; readC(r, b);

  auto n = (r-2)*(c-2), a = Matrix!real(n, n);
  auto idx(int i, int j) { return (i-1)*(c-2)+(j-1); }

  foreach (i; 1..r-1)
    foreach (j; 1..c-1) {
      if (b[i][j] == '#') continue;
      auto d = [b[i-1][j], b[i+1][j], b[i][j-1], b[i][j+1]].map!(bij => bij == '.' ? 1 : 0).sum;
      auto id1 = idx(i, j);
      if (d == 0) {
        a[id1][id1] = 1;
      } else {
        if (b[i-1][j] == '.') a[idx(i-1, j)][id1] = 1.0L/d;
        if (b[i+1][j] == '.') a[idx(i+1, j)][id1] = 1.0L/d;
        if (b[i][j-1] == '.') a[idx(i, j-1)][id1] = 1.0L/d;
        if (b[i][j+1] == '.') a[idx(i, j+1)][id1] = 1.0L/d;
      }
    }

  auto v = new real[](n);
  v[] = 0; v[idx(sx, sy)] = 1;

  auto p = repeatedSquare(a, t, Matrix!real.unit(n)) * v;
  writefln("%.7f", p[idx(gx, gy)]);
}

pure T repeatedSquare(alias pred = "a * b", T, U)(T a, U n)
{
  return repeatedSquare!(pred, T, U)(a, n, T(1));
}

pure T repeatedSquare(alias pred = "a * b", T, U)(T a, U n, T init)
{
  import std.functional;
  alias predFun = binaryFun!pred;

  if (n == 0) return init;

  auto r = init;
  while (n > 0) {
    if (n&1) r = predFun(r, a);
    a = predFun(a, a);
    n >>= 1;
  }

  return r;
}

struct Matrix(T)
{
  size_t r, c;
  T[][] a;
  alias a this;

  static ref auto unit(size_t n)
  {
    auto r = Matrix!T(n, n);
    foreach (i; 0..n) r[i][i] = 1;
    return r;
  }

  this(size_t r, size_t c)
  {
    this.r = r; this.c = c;
    a = new T[][](r, c);
    static if (T.init != 0) foreach (i; 0..r) a[i][] = 0;
  }

  this(T[][] b)
  {
    r = b.length;
    c = b[0].length;
    a = b;
  }

  ref auto dup() { auto x = Matrix!T(r, c); foreach (i; 0..r) x[i][] = a[i][]; return x; }

  ref auto opBinary(string op)(Matrix!T b) if (op == "+" || op == "-") in { assert(r == b.r && c == b.c); } body
  {
    auto x = Matrix!T(r, c);
    foreach (i; 0..r) foreach (j; 0..c) x[i][j] = mixin("a[i][j]"~op~"b[i][j]");
    return x;
  }

  ref auto opBinary(string op: "*")(Matrix!T b) in { assert(c == b.r); } body
  {
    auto x = Matrix!T(r, b.c);
    foreach (i; 0..r) foreach (j; 0..b.c) foreach (k; 0..c) x[i][j] += a[i][k]*b[k][j];
    return x;
  }

  ref auto opBinary(string op: "*")(T[] b) in { assert(c == b.length); } body
  {
    auto x = new T[](r);
    static if (T.init != 0) x[] = 0;
    foreach (i; 0..r) foreach (j; 0..c) x[i] += a[i][j]*b[j];
    return x;
  }
}
0