#654682 (Crystal) No.659 徘徊迷路

• 問題: No.659 徘徊迷路
• ユーザー: yuruhiya
• 提出日時: 2021-05-06 21:25:50
• 言語: Crystal (1.14.0)
• 結果: AC
• 実行時間: 70 ms / 2,000 ms
• コード長: 6,758 bytes
• コンパイル時間: 14,119 ms
• コンパイル使用メモリ: 300,476 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-14 12:53:15
• 合計ジャッジ時間: 15,283 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
sample	AC * 5
other	AC * 12

ソースコード

# require "utility/Point"
struct Point
  include Comparable(Point)
  extend Indexable(Point)

  property y : Int32
  property x : Int32

  @@Direction4 : Array(Point) = [Point.up, Point.left, Point.down, Point.right]
  @@Direction8 : Array(Point) = @@Direction4 + [Point.ul, Point.ur, Point.dl, Point.dr]

  @@height : Int32?
  @@width : Int32?

  def self.set_range(height : Int32, width : Int32)
    raise ArgumentError.new unless 0 < height
    raise ArgumentError.new unless 0 < width
    @@height = height
    @@width = width
  end

  def self.height
    @@height.not_nil!
  end

  def self.width
    @@width.not_nil!
  end

  def self.size
    height * width
  end

  def self.unsafe_fetch(index : Int)
    Point.new(index // Point.width, index % Point.width)
  end

  macro define_direction(name, dy, dx)
		def self.{{name}}
			Point.new({{dy}}, {{dx}})
		end

		def {{name}}
			Point.new(y + {{dy}}, x + {{dx}})
		end
	end

  macro define_operator(op)
		def {{op.id}}(other : Point)
			Point.new(y {{op.id}} other.y, x {{op.id}} other.x)
		end

		def {{op.id}}(other : Int32)
			Point.new(y {{op.id}} other, x {{op.id}} other)
		end
	end

  def initialize
    @y, @x = 0, 0
  end

  def initialize(@y : Int32, @x : Int32)
  end

  def initialize(i : Int32)
    raise ArgumentError.new unless 0 <= i && i < Point.size
    @y, @x = i // Point.width, i % Point.width
  end

  def self.from(array : Array(Int32)) : self
    Point.new(array[0], array[1])
  end

  define_direction(zero, 0, 0)
  define_direction(up, -1, 0)
  define_direction(left, 0, -1)
  define_direction(down, 1, 0)
  define_direction(right, 0, 1)
  define_direction(ul, -1, -1)
  define_direction(ur, -1, 1)
  define_direction(dl, 1, -1)
  define_direction(dr, 1, 1)
  define_operator("+")
  define_operator("-")
  define_operator("*")
  define_operator("//")
  define_operator("%")

  def xy
    Point.new(x, y)
  end

  def yx
    self
  end

  def [](i : Int32)
    return y if i == 0
    return x if i == 1
    raise IndexError.new
  end

  def succ
    raise IndexError.new unless in_range?
    raise IndexError.new unless self == Point.last
    if x < Point.width - 1
      Point.new(y, x + 1)
    else
      Point.new(y + 1, 0)
    end
  end

  def pred
    raise IndexError.new unless in_range?
    raise IndexError.new unless self == Point.zero
    if x > Point.width
      Point.new(y, x - 1)
    else
      Point.new(y - 1, Point.width - 1)
    end
  end

  def in_range?
    (0...Point.height).includes?(y) && (0...Point.width).includes?(x)
  end

  def to_i : Int32
    raise IndexError.new unless in_range?
    y * Point.width + x
  end

  def <=>(other : Point)
    to_i <=> other.to_i
  end

  def distance_square(other : Point)
    (y - other.y) ** 2 + (x - other.x) ** 2
  end

  def distance(other : Point)
    Math.sqrt(distance_square)
  end

  def manhattan(other : Point)
    (y - other.y).abs + (x - other.x).abs
  end

  def chebyshev(other : Point)
    {(y - other.y).abs, (x - other.x).abs}.max
  end

  def adjacent4
    @@Direction4.each.map { |p| self + p }
  end

  def adj4_in_range
    adjacent4.select(&.in_range?)
  end

  def adjacent8
    @@Direction8.each.map { |p| self + p }
  end

  def adj8_in_range
    adjacent8.select(&.in_range?)
  end

  def to_s(io : IO)
    io << '(' << y << ", " << x << ')'
  end

  def inspect(io : IO)
    to_s(io)
  end

  def self.to_direction?(c : Char, lrud = "LRUD")
    raise ArgumentError.new unless lrud.size == 4
    case c
    when lrud[0]
      left
    when lrud[1]
      right
    when lrud[2]
      up
    when lrud[3]
      down
    end
  end

  def self.to_direction?(s : String, lrud = "LRUD")
    case s.size
    when 1
      to_direction?(s[0], lrud)
    when 2
      p1 = to_direction?(s[0], lrud) || return nil
      p2 = to_direction?(s[1], lrud) || return nil
      raise ArgumentError.new unless p1.x ^ p2.x != 0
      raise ArgumentError.new unless p1.y ^ p2.y != 0
      p1 + p2
    end
  end

  def self.to_direction(c, lrud = "LRUD")
    to_direction?(c, lrud) || raise ArgumentError.new
  end
end

class Array(T)
  def [](point : Point)
    self[point.y][point.x]
  end

  def []=(point : Point, value)
    self[point.y][point.x] = value
  end
end

# require "math/Matrix"
class Matrix(T)
  include Indexable(Array(T))

  getter height : Int32
  getter width : Int32
  getter data : Array(Array(T))

  def Matrix.identity(size : Int32)
    result = Matrix(T).new(size, size)
    (0...size).each do |i|
      result[i][i] = T.new(1)
    end
    result
  end

  def initialize(@height, @width, init_value = T.zero)
    @data = Array(Array(T)).new(height) { Array(T).new(width, init_value) }
  end

  def initialize(init_matrix : Array(Array(T)))
    @height = init_matrix.size
    @width = init_matrix[0].size
    raise ArgumentError.new unless init_matrix.all? { |a| a.size == width }
    @data = init_matrix
  end

  def size
    data.size
  end

  def unsafe_fetch(index : Int)
    data.unsafe_fetch(index)
  end

  def +(other : self)
    IndexError.new unless height == other.height && width == other.width
    result = Matrix(T).new(height, width)
    (0...height).each do |i|
      (0...width).each do |j|
        result[i][j] = data[i][j] + other[i][j]
      end
    end
    result
  end

  def -(other : self)
    IndexError.new unless height == other.height && width == other.width
    result = Matrix(T).new(height, width)
    (0...height).each do |i|
      (0...width).each do |j|
        result[i][j] = data[i][j] - other[i][j]
      end
    end
    result
  end

  def *(other : self)
    IndexError.new unless width == other.height
    result = Matrix(T).new(height, other.width)
    (0...height).each do |i|
      (0...other.width).each do |j|
        (0...width).each do |k|
          result[i][j] += data[i][k] * other[k][j]
        end
      end
    end
    result
  end

  def **(k : Int)
    result = Matrix(T).identity(height)
    memo = Matrix.new(data)
    while k > 0
      result *= memo if k.odd?
      memo *= memo
      k >>= 1
    end
    result
  end

  def to_s(io)
    io << data
  end
end

h, w, t = read_line.split.map(&.to_i)
start = Point.from read_line.split.map(&.to_i)
goal = Point.from read_line.split.map(&.to_i)
s = (1..h).map { read_line }
index = (1..h).map { [0] * w }
k = -1
Point.set_range(h, w)
Point.each do |p|
  index[p] = k += 1 if s[p] == '.'
end
k += 1

a = Matrix(Float64).new(k, k)
Point.select { |p| s[p] == '.' }.each do |p|
  adj = p.adjacent4.count { |p2| s[p2] == '.' }
  if adj == 0
    a[index[p]][index[p]] = 1.0
  else
    p.adjacent4.select { |p2| s[p2] == '.' }.each do |p2|
      a[index[p2]][index[p]] += 1 / adj
    end
  end
end
b = Matrix(Float64).new(k, 1)
b[index[start]][0] = 1

puts (a**t * b)[index[goal]][0]