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 |
Referenced site
Recommended Posts