幅優先探索をマスターした - 主夫ときどきプログラマ

f:id:masayuki14:20201122142454j:plain

最近はあまりAtCoderできてなかったけど、勉強会で幅優先探索をやった。勉強会やっておけば強制的に時間をつくれるので、ゆるく長く続けるにはオススメ。

幅優先探索はQueueを使う

幅優先探索にはQueueを使う。Rubyでは配列を使えばよい。Queueに入れるときは push() で出すときは shift() を使う。

irb(main):001:0> q = []
=> []
irb(main):002:0> q.push(1)
=> [1]
irb(main):003:0> q.push(2)
=> [1, 2]
irb(main):004:0> q.shift()
=> 1
irb(main):005:0> q
=> [2]
irb(main):006:0> q.push(3)
=> [2, 3]
irb(main):007:0>

っていう感じ。

ABC 088 D - Grid Repainting

今回は AtCoder Beginner Contest 088 D - Grid Repainting の問題に取り組んだ。解けるまで60分位かかったので、実際のコンテストで出たら解けるかどうか・・・ギリギリのところだろう。

解のポイントとしては、迷路のスタートからゴールまでの最短距離を求めてやれば、あとは白マスの数から引き算すればいいよね、っていう問題。書いたコードはこちら。Queueには次に探索するマスをどんどん突っ込んで、順に進んでいくように実装する。

(H, W) = gets.chomp.split.map(&:to_i)
maze = readlines.map{ |l| l.chomp.split('') }

gx = H - 1
gy = W - 1

cost = Array.new(H) { Array.new(W) { nil } } # そのマスまでの距離
cost[0][0] = 1

q = [[0, 0]] # スタート座標

while q.length > 0 do
  (x, y) = q.shift

  # 次に進むマス
  [[x+1,y], [x-1,y], [x,y+1], [x,y-1]].each do |n|
    (nx, ny) = n
    # goalについた
    if nx == gx && ny == gy && cost[nx][ny].nil?
      cost[nx][ny] = cost[x][y] + 1
      break
    end

    # 次のマスが移動可能で、まだ行ってないなら進む
    if nx >= 0 && nx < H && ny >= 0 && ny < W && maze.[](nx)&.[](ny) == '.' && cost[nx][ny].nil?
      cost[nx][ny] = cost[x][y] + 1
      q.push([nx, ny])
    end
  end
end

if cost[gx][gy].nil?
  puts -1
else
  white = maze.flatten.reject{|m| m == '#'}.length
  puts white - cost[gx][gy]
end