kotazon.com

虎太郎の備忘録

【AtCoder-Ruby】ARC012 C - 五目並べチェッカー

AtCoder

これを見て挑戦！

「白と黒の合計のチェック」と「5個連続のチェック」でうまくいくと思ったが、うまくいかず。。。

とりあえず、この助言を参考に実装

  • 黒石と白石の数は、一致しているか黒石が１つ多くなければらない。そうでなければ到達不可。
  • 最後に石を打った番の方は、１つ石を取り除くと５石連続しない（そうしないと途中で対戦が終了しているから）
  • 最後に石を打った番でない方は、５石連続しない。

出典

碁のルールを知らず、5個以上の塊と勘違いしていた。。。
連続なのだから直線！

こちらを参考にさせて頂きました。m(__)m
betrue12

回答

# - 白と黒の石は同じか黒が1つ多い
# - 白と黒両方が勝つことはない
# - 5石連続は1つ（2つはない）
# - 勝った方は、１つ石を取り除くと５石連続しない（そうしないと途中で対戦が終了しているから）

CHAIN = 5
N = 19
W = "x"
B = "o"

LINE = [
  [0, N - CHAIN, 0, N - 1, CHAIN.times.map { |i| [i, 0] }],          # 右
  [0, N - 1, 0, N - CHAIN, CHAIN.times.map { |i| [0, i] }],          # 下
  [0, N - CHAIN, 0, N - CHAIN, CHAIN.times.map { |i| [i, i] }],      # 斜め右下
  [CHAIN - 1, N - 1, 0, N - CHAIN, CHAIN.times.map { |i| [-i, i] }], # 斜め左下
]

@bord = N.times.map { gets.strip }

def fin(yes)
  puts yes ? "YES" : "NO"
  exit
end

def is_win(bw)
  win = false
  N.times do |i|
    N.times do |j|
      LINE.each do |x1, x2, y1, y2, ary|
        next unless i.between?(x1, x2) && j.between?(y1, y2)
        if ary.all? { |x, y| @bord[i+x][j+y].eql?(bw) }
          win = true
          break  
        end
      end
      break if win
    end
    break if win
  end
  win
end

bc = 0
wc = 0

N.times do |i|
  bws = @bord[i].scan(/[xo]/)
  next if bws.size.zero?
  bc += bws.count(B)
  wc += bws.count(W)
end

# 白と黒の石は同じか黒が1つ多い
if bc.eql?(wc) || bc.eql?(wc + 1)
  b_win = is_win(B)
  w_win = is_win(W)

  # 白黒両方勝ちはない
  fin(false) if b_win && w_win

  # 継続中（勝ち負けなし）の場合
  fin(true) if !b_win && !w_win

  # 白黒どちらかが勝っている
  bw = b_win ? B : W

  # 黒勝ちの時、白は黒の数 -1（黒勝ちの時、黒白同じ数はない）
  fin(false) if bw.eql?(B) && bc.eql?(wc)
  
  # 白勝ちの時、白は黒は同じ数
  fin(false) if bw.eql?(W) && bc.eql?(wc + 1)

  # 勝った方は、１つ石を取り除くと５石連続しない状態がある（そうしないと途中で対戦が終了しているから）
  N.times do |i|
    N.times do |j|
      if @bord[i][j].eql?(bw)
        @bord[i][j] = '.'
        fin(true) unless is_win(bw)
        @bord[i][j] = bw
      end
    end
  end
end

fin(false)

だめなやつだけど貼っておく

だめなところは、連続の捉え方が間違っているところ。
塊ではだめ。

# - 白と黒の石は同じか黒が1つ多い
# - 白と黒両方が勝つことはない
# - 5石連続は1つ（2つはない）
# - 勝った方は、１つ石を取り除くと５石連続しない（そうしないと途中で対戦が終了しているから）

N = 19
W = "x"
B = "o"

@bord = N.times.map { gets.strip }

def fin(yes)
  puts yes ? "YES" : "NO"
  exit
end

def get_chains(bw)
  map = Array.new(N) { Array.new(N) { true } }

  mv = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]

  chains = []

  N.times do |i|
    N.times do |j|
      if @bord[i][j].eql?(bw)
        queue = [[j, i]]     
        chain = 0
        until queue.size.zero?
          x, y = queue.shift
          mv.each do |m|
            next_x = m.first + x
            next_y = m.last  + y
            if next_x >= 0 && next_x < N &&
               next_y >= 0 && next_y < N && 
               map[next_y][next_x] && @bord[next_y][next_x].eql?(bw)

                chain += 1
                map[next_y][next_x] = false

                queue.push([next_x, next_y])
            end
          end
        end
        chains << chain if chain >= 5
      end
    end
  end
  chains
end

bc = 0
wc = 0

N.times do |i|
  bws = @bord[i].scan(/[xo]/)
  next if bws.size.zero?
  bc += bws.count(B)
  wc += bws.count(W)
end

# 白と黒の石は同じか黒が1つ多い
if bc.eql?(wc) || bc.eql?(wc + 1)
  b_chains = get_chains(B)
  w_chains = get_chains(W)

  # 5石連続は1つ以上ない
  fin(false) if b_chains.size > 1 || w_chains.size > 1

  # 白黒両方に5石連続はない
  fin(false) if b_chains.size.eql?(1) && w_chains.size.eql?(1)

  # 継続中（勝ち負けなし）の場合
  fin(true) if b_chains.size.eql?(0) && w_chains.size.eql?(0)

  # 白黒どちらかが勝っている
  bw = b_chains.size > 0 ? B : W
  bw_max = b_chains.size > 0 ? b_chains.first : w_chains.first

  # 黒勝ちの時、白は黒の数 -1（黒勝ちの時、黒白同じ数はない）
  fin(false) if bw.eql?(B) && bc.eql?(wc)
  
  # 白勝ちの時、白は黒は同じ数
  fin(false) if bw.eql?(W) && bc.eql?(wc + 1)

  # 勝った方は、１つ石を取り除くと５石連続しない状態がある（そうしないと途中で対戦が終了しているから）
  N.times do |i|
    N.times do |j|
      if @bord[i][j].eql?(bw)
        @bord[i][j] = '.'
        fin(true) if get_chains(bw).size.zero?
        @bord[i][j] = bw
      end
    end
  end
end

fin(false)

考察

強い人のソースは参考になる。