Solving with Ruby and Python AtCoder ABC151 D Breadth-first search

Introduction

• AtCoder Problems * Use Recommendations to solve past problems. Thanks to AtCoder and AtCoder Problems.

This theme

AtCoder Beginner Contest D - Maze Master Difficulty: 969

This theme, breadth-first search

Since it is a width priority search, it is a basic * solve with Ruby, Perl, Java and Python AtCoder ATC 002 A -Qiita * and an application * Ruby and Perl Customize AtCoder AGC 033 A Width Priority Search -Qiita * to solve in Java and Python. This time, the constraint is loose as 1 ≤ H, W ≤ 20, so we will investigate all . as the starting point. 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

All . are registered as starting points.

Marshal.rb

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

It fits with a shallow copy. Make a deep copy with 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)

*** A deep copy of Python *** is deepcopy

Summary

• Solved ABC 151 D
• Become familiar with Ruby
• Become familiar with Python

Referenced site

• Three types of Ruby variable copying methods from the viewpoint of destructive operation -Qiita *
• About Python copy and deep copy -Qiita * instance method Object#clone