AtCoder Beginner Contest D - Maze Master Difficulty: 969
Ce thème, recherche de priorité de largeur
Puisqu'il s'agit d'une recherche avec priorité à la largeur, il s'agit d'une * résoudre avec Ruby, Perl, Java et Python AtCoder ATC 002 A -Qiita * et une application * Ruby et Perl Personnaliser AtCoder AGC 033 Une recherche de priorité de largeur -Qiita * pour résoudre en Java et Python. Cette fois, la contrainte est lâche comme «1 ≤ H, W ≤ 20», nous allons donc étudier tout «.» Comme point de départ. 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
Tous les «.» Sont enregistrés comme points de départ.
Marshal.rb
dm = Marshal.load(Marshal.dump(cm))
Il s'adapte à une copie peu profonde. Faites une copie complète avec 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)
*** Une copie profonde de Python *** est deepcopy
| Ruby | Python | |
|---|---|---|
| Longueur du code(Byte) | 832 | 1502 |
| Temps d'exécution(ms) | 112 | 328 |
| Mémoire(KB) | 2428 | 3572 |
Site référencé
Recommended Posts