#674685 (Crystal) No.1588 Connection

提出ソース

結果

問題	No.1588 Connection
ユーザー	yuruhiya
提出日時	2021-07-09 14:23:14
言語	Crystal (1.11.2)
結果	AC
実行時間	109 ms / 2,000 ms
コード長	5,868 bytes
コンパイル時間	11,595 ms
コンパイル使用メモリ	296,556 KB
実行使用メモリ	25,500 KB
平均クエリ数	484.41
最終ジャッジ日時	2024-07-17 12:57:07
合計ジャッジ時間	14,885 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	38 ms 25,500 KB
testcase_01	AC	23 ms 24,836 KB
testcase_02	AC	24 ms 25,220 KB
testcase_03	AC	22 ms 24,964 KB
testcase_04	AC	23 ms 24,964 KB
testcase_05	AC	24 ms 24,952 KB
testcase_06	AC	24 ms 24,836 KB
testcase_07	AC	23 ms 25,220 KB
testcase_08	AC	25 ms 25,220 KB
testcase_09	AC	24 ms 25,220 KB
testcase_10	AC	25 ms 24,964 KB
testcase_11	AC	25 ms 24,836 KB
testcase_12	AC	28 ms 24,836 KB
testcase_13	AC	29 ms 25,220 KB
testcase_14	AC	24 ms 25,220 KB
testcase_15	AC	24 ms 24,836 KB
testcase_16	AC	24 ms 25,220 KB
testcase_17	AC	23 ms 25,220 KB
testcase_18	AC	23 ms 24,964 KB
testcase_19	AC	24 ms 24,964 KB
testcase_20	AC	25 ms 24,964 KB
testcase_21	AC	107 ms 24,836 KB
testcase_22	AC	107 ms 24,836 KB
testcase_23	AC	57 ms 24,964 KB
testcase_24	AC	40 ms 24,964 KB
testcase_25	AC	66 ms 25,204 KB
testcase_26	AC	64 ms 24,580 KB
testcase_27	AC	41 ms 25,220 KB
testcase_28	AC	36 ms 24,964 KB
testcase_29	AC	108 ms 24,964 KB
testcase_30	AC	109 ms 25,220 KB
testcase_31	AC	22 ms 24,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

# 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

yukicoder

結果

テストケース

ソースコード