結果

問題 No.1588 Connection
ユーザー yuruhiyayuruhiya
提出日時 2021-07-09 14:23:14
言語 Crystal
(1.11.2)
結果
AC  
実行時間 116 ms / 2,000 ms
コード長 5,868 bytes
コンパイル時間 18,640 ms
コンパイル使用メモリ 256,632 KB
実行使用メモリ 24,276 KB
平均クエリ数 484.41
最終ジャッジ日時 2023-09-24 12:02:09
合計ジャッジ時間 20,547 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
23,712 KB
testcase_01 AC 25 ms
23,304 KB
testcase_02 AC 26 ms
24,252 KB
testcase_03 AC 25 ms
23,616 KB
testcase_04 AC 26 ms
23,916 KB
testcase_05 AC 27 ms
23,916 KB
testcase_06 AC 26 ms
23,544 KB
testcase_07 AC 26 ms
23,544 KB
testcase_08 AC 29 ms
23,268 KB
testcase_09 AC 28 ms
23,916 KB
testcase_10 AC 26 ms
24,276 KB
testcase_11 AC 28 ms
23,460 KB
testcase_12 AC 30 ms
23,976 KB
testcase_13 AC 33 ms
23,712 KB
testcase_14 AC 28 ms
24,108 KB
testcase_15 AC 28 ms
23,316 KB
testcase_16 AC 26 ms
23,292 KB
testcase_17 AC 27 ms
24,252 KB
testcase_18 AC 28 ms
23,268 KB
testcase_19 AC 28 ms
24,120 KB
testcase_20 AC 29 ms
23,424 KB
testcase_21 AC 114 ms
23,604 KB
testcase_22 AC 116 ms
24,108 KB
testcase_23 AC 62 ms
23,268 KB
testcase_24 AC 44 ms
23,532 KB
testcase_25 AC 73 ms
23,544 KB
testcase_26 AC 72 ms
23,604 KB
testcase_27 AC 47 ms
23,892 KB
testcase_28 AC 40 ms
24,096 KB
testcase_29 AC 114 ms
23,556 KB
testcase_30 AC 113 ms
23,256 KB
testcase_31 AC 25 ms
24,108 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

  property y : Int32, x : Int32

  Direction4 = [Point.up, Point.left, Point.down, Point.right]
  Direction8 = Direction4 + [Point.ul, Point.ur, Point.dl, Point.dr]

  class_getter! height : Int32, width : Int32

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

  def self.size
    height * width
  end

  def self.unsafe_fetch(index : Int)
    Point.new(index // Point.width, index % Point.width)
  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
    raise ArgumentError.new unless array.size == 2
    Point.new(array.unsafe_fetch(0), array.unsafe_fetch(1))
  end

  def self.[](y : Int32, x : Int32) : self
    Point.new(y, x)
  end

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

    def {{name}}
      Point.new(y + {{dy}}, x + {{dx}})
    end
  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)

  {% for op in %w[+ - * // %] %}
    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 xy
    Point.new(x, y)
  end

  def yx
    self
  end

  def ==(other : Point)
    x == other.x && y == other.y
  end

  def <=>(other : Point)
    to_i <=> other.to_i
  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? && 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? && self != Point.first
    if x > 0
      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 distance_square(other : Point)
    (y - other.y) ** 2 + (x - other.x) ** 2
  end

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

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

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

  {% for i in [4, 8] %}
    def adjacent{{i}}(&block) : Nil
      Direction{{i}}.each do |d|
        yield self + d
      end
    end

    def adjacent{{i}}
      Direction{{i}}.each.map { |p| self + p }
    end

    def adj{{i}}_in_range(&block) : Nil
      Direction{{i}}.each do |d|
        point = self + d
        yield point if point.in_range?
      end
    end

    def adj{{i}}_in_range
      adjacent{{i}}.select(&.in_range?)
    end
  {% end %}

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

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

  def to_direction_char?(lrud = "LRUD") : Char?
    if y == 0 && x != 0
      x < 0 ? lrud[0] : lrud[1]
    elsif x == 0 && y != 0
      y < 0 ? lrud[2] : lrud[3]
    end
  end

  def self.to_direction?(c : Char, lrud = "LRUD")
    raise ArgumentError.new unless lrud.size == 4
    lrud.index(c).try { |i| {left, right, up, down}[i] }
  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
      return nil unless p1.x ^ p2.x != 0 && p1.y ^ p2.y != 0
      p1 + p2
    end
  end
end

module Indexable(T)
  private def check_index_out_of_bounds(point : Point)
    check_index_out_of_bounds(point) { raise IndexError.new }
  end

  private def check_index_out_of_bounds(point : Point)
    if 0 <= point.y < size && 0 <= point.x < unsafe_fetch(point.y).size
      point
    else
      yield
    end
  end

  def fetch(point : Point)
    point = check_index_out_of_bounds(point) do
      return yield point
    end
    unsafe_fetch(point.y)[point.x]
  end

  def [](point : Point)
    fetch(point) { raise IndexError.new }
  end

  def []?(point : Point)
    fetch(point, nil)
  end
end

class Array(T)
  def []=(point : Point, value)
    index = check_index_out_of_bounds point
    @buffer[index.y][index.x] = value
  end
end

class Manager
  getter n : Int32, m : Int32

  def initialize
    @n, @m = read_line.split.map(&.to_i)
    Point.set_range(@n, @n)
    @black = Set(Point).new
    @black << Point.first << Point.last
    @white = Set(Point).new
  end

  def black?(p : Point)
    if @black.size == @m
      false
    elsif @black.includes?(p)
      true
    elsif @white.includes?(p)
      false
    else
      puts "#{p.y + 1} #{p.x + 1}"; STDOUT.flush
      s = read_line
      if s == "Black"
        @black << p
        true
      elsif s == "White"
        @white << p
        false
      else
        exit
      end
    end
  end
end

a = Manager.new
que = Deque{Point.first}
vis = Set{Point.first}
while p = que.pop?
  p.adj4_in_range do |p2|
    if a.black?(p2)
      unless vis.includes?(p2)
        vis << p2
        que << p2
      end
      if p2.manhattan(Point.last) == 1
        puts "Yes"; STDOUT.flush
        exit
      end
    end
  end
end
puts "No"; STDOUT.flush
0