Ruby と Python で解く AtCoder ABC151 D 幅優先探索

はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

AtCoder Beginner Contest D - Maze Master
Difficulty: 969

今回のテーマ、幅優先探索

幅優先探索ですから、基本となる Ruby と Perl と Java と Python で解く AtCoder ATC 002 A -Qiita や応用の Ruby と Perl と Java と Python で解く AtCoder AGC 033 A 幅優先探索 -Qiita をカスタマイズします。
今回は制約が1≤H,W≤20と緩いので、全ての.をスタート地点として調査します。

Ruby

ruby.rb

h, w = gets.split.map(&:to_i)
cm = Array.new(h + 2){Array.new(w + 2, 0)}
que = []
a = []
1.upto(h) do |i|
  s = gets.chomp
  1.upto(w) do |j|
    if s[j - 1] == '.'
      cm[i][j] = -1
      a << [i, j]
    end
  end
end
ans = 0
a.each do |b|
  dm = Marshal.load(Marshal.dump(cm))
  que << [b[0], b[1], 0]
  dm[b[0]][b[1]] = 0
  while que.size > 0
    y, x, r = que.shift
    ans = r + 1 if ans < r + 1
    if dm[y + 1][x] == -1
      dm[y + 1][x] = r + 1
      que << [y + 1, x, r + 1]
    end
    if dm[y - 1][x] == -1
      dm[y - 1][x] = r + 1
      que << [y - 1, x, r + 1]
    end
    if dm[y][x - 1] == -1
      dm[y][x - 1] = r + 1
      que << [y, x - 1, r + 1]
    end
    if dm[y][x + 1] == -1
      dm[y][x + 1] = r + 1
      que << [y, x + 1, r + 1]
    end
  end
end
puts ans - 1

que.rb

    if s[j - 1] == '.'
      cm[i][j] = -1
      a << [i, j]
    end

全ての.をスタート地点として登録しています。

Marshal.rb

  dm = Marshal.load(Marshal.dump(cm))

浅いコピーで嵌りました。Marshalで深いコピーをします。

Python

from sys import stdin

def main():
    from collections import deque
    import copy
    input = stdin.readline

    h, w = map(int, input().split())
    cm = [[0] * (w + 2) for _ in range(h + 2)]
    que = deque([])
    a = deque([])
    for i in range(1, h + 1):
        s = input()
        for j in range(1, w + 2):
            if s[j - 1] == ".":
                cm[i][j] = -1
                a.append([i, j])
    ans = 0
    for b in a:
        dm = copy.deepcopy(cm)
        que.append(b[0])
        que.append(b[1])
        que.append(0)
        dm[b[0]][b[1]] = 0
        while len(que) > 0:
            y = que.popleft()
            x = que.popleft()
            r = que.popleft()
            if ans < r + 1:
                ans = r + 1
            if dm[y + 1][x] == -1:
                dm[y + 1][x] = r + 1
                que.append(y + 1)
                que.append(x)
                que.append(r + 1)
            if dm[y - 1][x] == -1:
                dm[y - 1][x] = r + 1
                que.append(y - 1)
                que.append(x)
                que.append(r + 1)
            if dm[y][x + 1] == -1:
                dm[y][x + 1] = r + 1
                que.append(y)
                que.append(x + 1)
                que.append(r + 1)
            if dm[y][x - 1] == -1:
                dm[y][x - 1] = r + 1
                que.append(y)
                que.append(x - 1)
                que.append(r + 1)
    print(ans - 1)
main()

deepcopy.py

        dm = copy.deepcopy(cm)

Python の深いコピーはdeepcopyです

	Ruby	Python
コード長 (Byte)	832	1502
実行時間 (ms)	112	328
メモリ (KB)	2428	3572

まとめ

• ABC 151 D を解いた
• Ruby に詳しくなった
• Python に詳しくなった

参照したサイト
破壊的操作の観点から見たRubyの変数コピーの方法３種類 -Qiita
Pythonのcopyとdeepcopyについて -Qiita
instance method Object#clone