# AtCoder Grand Contest 043

URL: https://atcoder.jp/contests/agc043 (opens new window)

# D

h,w = gets.chomp.split(" ").map(&:to_i)
maze = h.times.map{gets.chomp}

MAX = 10 ** 9
dp = Array.new(h) { Array.new(w, MAX) }
dp[0][0] = maze[0][0] == "#" ? 1 : 0

(0..h-1).each do |y|
  (0..w-1).each do |x|
    # 下 or 右
    [[1, 0], [0, 1]].each do |(dy, dx)|
      tmp_y = y + dy
      tmp_x = x + dx
      next if tmp_y >= h || tmp_x >= w
      if maze[tmp_y][tmp_x] == "#" && maze[y][x] == "."
        dp[tmp_y][tmp_x] = [dp[tmp_y][tmp_x], dp[y][x] + 1].min
      else
        dp[tmp_y][tmp_x] = [dp[tmp_y][tmp_x], dp[y][x]].min
      end
    end
  end
end

puts dp[-1][-1]
Last Updated: 2020/08/15 20:23