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

# はじめに
*[AtCoder Problems](https://kenkoooo.com/atcoder/#/)* の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

# 今回のお題
*[AtCoder Beginner Contest D - Maze Master](https://atcoder.jp/contests/abc151/tasks/abc151_d)*
<font color="green">Difficulty: 969</font>

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

幅優先探索ですから、基本となる *[Ruby と Perl と Java と Python で解く AtCoder ATC 002 A -Qiita](https://qiita.com/superrino130/items/7f314086fc6ea01af410)* や応用の *[Ruby と Perl と Java と Python で解く AtCoder AGC 033 A 幅優先探索 -Qiita](https://qiita.com/superrino130/items/5d3059a100e23bcbbe37)* をカスタマイズします。
今回は制約が`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
```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](https://qiita.com/metheglin/items/d4992f82aa296f348f10)*
*[Pythonのcopyとdeepcopyについて -Qiita](https://qiita.com/Kaz_K/items/a3d619b9e670e689b6db)*
*[instance method Object#clone](https://docs.ruby-lang.org/ja/latest/method/Object/i/clone.html)*