結果

問題 No.2412 YOU Grow Bigger!
ユーザー tomerun
提出日時 2023-08-11 22:49:29
言語 Crystal
(1.14.0)
結果
WA  
実行時間 -
コード長 1,821 bytes
コンパイル時間 13,688 ms
コンパイル使用メモリ 295,136 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-18 17:56:40
合計ジャッジ時間 11,756 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

h, w = read_line.split.map(&.to_i)
s = Array.new(h) { read_line.chars.map { |ch| ch == '#' } }
h.times do |i|
  w.times do |j|
    if s[i][j]
      -2.upto(0) do |dy|
        -2.upto(0) do |dx|
          ny = i + dy
          nx = j + dx
          next if ny < 0 || h <= ny || nx < 0 || w <= nx
          s[ny][nx] = true
        end
      end
    end
  end
end
g = Array.new(h * w + 2) { [] of Tuple(Int32, Int32) }
start = h * w
goal = h * w + 1
3.times do |i|
  1.upto(h - 1) do |j|
    g[start] << {j * w + i, 1}
  end
end
(h - 3).upto(h - 1) do |i|
  0.upto(w - 4) do |j|
    g[start] << {i * w + j, 1}
  end
end
h.times do |i|
  if s[i][0]
    g[start] << {i * w, 0}
  end
  g[i * w + w - 1] << {goal, 0} if i < h - 3
end
w.times do |i|
  if s[h - 1][i]
    g[start] << {(h - 1) * w + i, 0}
  end
  g[i] << {goal, 0} if i > 0
end
h.times do |i|
  w.times do |j|
    if i > 0 && s[i - 1][j]
      g[i * w + j] << {(i - 1) * w + j, 0}
    end
    if i < h - 1 && s[i + 1][j]
      g[i * w + j] << {(i + 1) * w + j, 0}
    end
    if j > 0 && s[i][j - 1]
      g[i * w + j] << {i * w + j - 1, 0}
    end
    if j < w - 1 && s[i][j + 1]
      g[i * w + j] << {i * w + j + 1, 0}
    end
    -3.upto(3) do |dy|
      -3.upto(3) do |dx|
        next if dy.abs + dx.abs == 6
        ny = i + dy
        nx = j + dx
        next if ny < 0 || h <= ny || nx < 0 || w <= nx
        next if ny == 0 && nx == 0
        next if ny >= h - 3 && nx >= w - 3
        g[i * w + j] << {ny * w + nx, 1}
      end
    end
  end
end
dist = Array.new(g.size, 1 << 29)
dist[start] = 0
q = Deque.new([{start, 0}])
while !q.empty?
  cp, cd = q.shift
  g[cp].each do |adj, d|
    nd = cd + d
    next if dist[adj] <= nd
    dist[adj] = nd
    if d == 0
      q.unshift({adj, nd})
    else
      q << {adj, nd}
    end
  end
end
puts dist[goal]
0