結果

問題 No.424 立体迷路
ユーザー simansiman
提出日時 2020-12-22 18:04:36
言語 Ruby
(3.4.1)
結果
AC  
実行時間 94 ms / 2,000 ms
コード長 1,549 bytes
コンパイル時間 271 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 12,416 KB
最終ジャッジ日時 2024-09-21 14:16:20
合計ジャッジ時間 3,775 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 5
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:81: warning: assigned but unused variable - nnz
Syntax OK

ソースコード

diff #
プレゼンテーションモードにする

class UnionFind
def initialize(n)
@size = Array.new(n, 1)
@rank = Array.new(n, 0)
@parent = []
(0..n).each do |i|
@parent[i] = i
end
end
def find(x)
if @parent[x] == x
x
else
@parent[x] = find(@parent[x])
end
end
def unite(x, y)
x = find(x)
y = find(y)
return if x == y
if @rank[x] < @rank[y]
@parent[x] = y
@size[y] += @size[x]
else
@parent[y] = x
@size[x] += @size[y]
@rank[x] += 1 if @rank[x] == @rank[y]
end
end
def same?(x, y)
find(x) == find(y)
end
def size(x)
@size[find(x)]
end
end
H, W = gets.split.map(&:to_i)
SY, SX, GY, GX = gets.split.map(&:to_i)
B = H.times.map { gets.chomp.chars.map(&:to_i) }
uf = UnionFind.new(10_000)
def calc_z(y, x)
y * W + x
end
DY = [-1, 0, 1, 0, -2, 0, 2, 0]
DX = [0, 1, 0, -1, 0, 2, 0, -2]
H.times do |y|
W.times do |x|
h = B[y][x]
z = calc_z(y, x)
8.times do |i|
ny = y + DY[i]
nx = x + DX[i]
nz = calc_z(ny, nx)
next if ny < 0 || nx < 0 || H <= ny || W <= nx
next if uf.same?(z, nz)
nh = B[ny][nx]
if i < 4
d = (h - nh).abs
next if d >= 2
uf.unite(z, nz)
else
next if h != nh
nny = y + DY[i - 4]
nnx = x + DX[i - 4]
nnz = calc_z(nny, nnx)
nnh = B[nny][nnx]
next if h <= nnh
uf.unite(z, nz)
end
end
end
end
if uf.same?(calc_z(SY - 1, SX - 1), calc_z(GY - 1, GX - 1))
puts 'YES'
else
puts 'NO'
end
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0