AtCoder Beginner Contest D - Maze Master Difficulty: 969
Dieses Thema, Breite Priorität Suche
Da es sich um eine Suche mit Breitenpriorität handelt, handelt es sich um eine grundlegende * Lösung mit Ruby, Perl, Java und Python AtCoder ATC 002 A -Qiita * und eine Anwendung * Ruby und Perl Passen Sie AtCoder AGC 033 A Width Priority Search -Qiita * an, um es in Java und Python zu lösen. Dieses Mal ist die Bedingung locker als "1 ≤ H, W ≤ 20", also werden wir alle "." Als Ausgangspunkt untersuchen. 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
Alle . sind als Startpunkte registriert.
Marshal.rb
dm = Marshal.load(Marshal.dump(cm))
Es passt zu einer flachen Kopie. Machen Sie eine tiefe Kopie mit "Marschall". 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)
*** Eine tiefe Kopie von Python *** ist "Deepcopy"
| Ruby | Python | |
|---|---|---|
| Codelänge(Byte) | 832 | 1502 |
| Ausführungszeit(ms) | 112 | 328 |
| Erinnerung(KB) | 2428 | 3572 |
Referenzierte Site
Recommended Posts