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

Introduction

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

Ruby Python
Code length(Byte) 832 1502
Execution time(ms) 112 328
memory(KB) 2428 3572

Summary

Referenced site

Recommended Posts

Solving with Ruby and Python AtCoder ABC151 D Breadth-first search
Solving with Ruby and Python AtCoder ABC178 D Dynamic programming
Solving with Ruby and Python AtCoder ABC138 D Adjacency list
Solving with Ruby, Python and networkx AtCoder ABC168 D Adjacency list
Solving with Ruby and Python AtCoder ABC057 C Prime Factorization Bit Search
Solving with Ruby, Perl, Java, and Python AtCoder AGC 033 A Breadth-first search
Solving with Ruby, Perl, Java and Python AtCoder ABC 165 D Floor function
Solving with Ruby, Perl, Java and Python AtCoder ABC 131 D Array Sorting
Solve with Ruby and Python AtCoder ABC133 D Cumulative sum
Solving with Ruby and Python AtCoder AISING2020 D Iterative Squares
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
Solving with Ruby and Python AtCoder ABC153 E Dynamic programming
Solving in Ruby, Python and Java AtCoder ABC141 D Priority Queuing
Solving with Ruby, Python and numpy AtCoder ABC054 B Matrix operation
Solving with Ruby, Perl, Java, and Python AtCoder ABC 065 C factorial
Solving with Ruby, Perl, Java and Python AtCoder ABC 107 B String Manipulation
AtCoder ABC130 D Cumulative Sum Binary Search Solved by Ruby and Python
Solve with Ruby and Python AtCoder ABC084 D Cumulative sum of prime numbers
Solving with Ruby and Python AtCoder ARC 059 C Least Squares
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 A
Solving with Ruby and Python AtCoder ARC067 C Prime Factorization
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 B
Solve AtCoder ABC168 with python (A ~ D)
Solving with Ruby AtCoder ABC110 C String Manipulation
Solving with Ruby, Perl, Java, and Python AtCoder ARC 098 C Cumulative sum
Solving with Ruby, Perl, Java and Python AtCoder CADDi 2018 C Prime Factorization
Solving with Ruby and Python AtCoder Tenka1 Programmer Contest C Cumulative sum
AtCoder ABC172 C Cumulative Sum Binary Search Solved by Ruby and Python
Solve with Ruby, Perl, Java and Python AtCoder ABC 047 C Regular Expression
Solve AtCoder ABC166 with python
AtCoder ABC 182 Python (A ~ D)
[Python] Depth-first search and breadth-first search
Solve AtCoder ABC 186 with Python
AtCoder ARC080 D simulation solved in Ruby and Python
Solving with Ruby and Python AtCoder CODE FESTIVAL 2016 qual C B Priority queue
AtCoder ABC155 Problem D Pairs Review Note 2 NumPy and Python
Scraping with Node, Ruby and Python
Solve ABC166 A ~ D with Python
Solving with Ruby, Perl, Java and Python AtCoder diverta 2019 Programming Contest C String Manipulation
Solved AtCoder ABC 114 C-755 with Python3
AtCoder ABC168 A case expression solved in Ruby and Python
Solve with Ruby, Python and Java AtCoder ARC104 B Cumulative sum
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Encrypt with Ruby (Rails) and decrypt with Python
Easy web scraping with Python and Ruby
AtCoder ABC 174 Python
AtCoder ABC187 Python
AtCoder ABC188 Python
AtCoder ABC 175 Python
Solve with Python [100 past questions that beginners and intermediates should solve] (028 --033 breadth-first search)
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
Automatically search and download YouTube videos with Python
Causal reasoning and causal search with Python (for beginners)
Solving the Lorenz 96 model with Julia and Python
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
[AtCoder explanation] Control the A, B, C, D problems of ABC183 with Python!
Solving in Ruby, Perl, Java, and Python AtCoder ARC 066 C Iterative Squares Hash
[AtCoder explanation] Control the A, B, C, D problems of ABC181 with Python!
Sequential search with Python
Solve AtCoder 167 with python
Python Exercise 1-Breadth-first search