結果

問題 No.659 徘徊迷路
ユーザー yuruhiyayuruhiya
提出日時 2021-05-06 21:25:50
言語 Crystal
(1.11.2)
結果
AC  
実行時間 72 ms / 2,000 ms
コード長 6,758 bytes
コンパイル時間 20,748 ms
コンパイル使用メモリ 262,840 KB
実行使用メモリ 5,264 KB
最終ジャッジ日時 2023-10-12 13:59:03
合計ジャッジ時間 22,064 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,452 KB
testcase_01 AC 11 ms
4,784 KB
testcase_02 AC 3 ms
4,468 KB
testcase_03 AC 3 ms
4,524 KB
testcase_04 AC 6 ms
4,848 KB
testcase_05 AC 2 ms
4,560 KB
testcase_06 AC 3 ms
4,480 KB
testcase_07 AC 3 ms
4,404 KB
testcase_08 AC 8 ms
4,856 KB
testcase_09 AC 16 ms
4,864 KB
testcase_10 AC 33 ms
5,136 KB
testcase_11 AC 65 ms
5,264 KB
testcase_12 AC 8 ms
4,852 KB
testcase_13 AC 61 ms
5,092 KB
testcase_14 AC 61 ms
5,188 KB
testcase_15 AC 71 ms
5,204 KB
testcase_16 AC 72 ms
5,244 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 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]
0