結果

問題 No.2412 YOU Grow Bigger!
コンテスト
ユーザー tomerun
提出日時 2023-08-11 23:18:58
言語 Crystal
(1.14.0)
結果
WA  
実行時間 -
コード長 2,595 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 11,810 ms
コンパイル使用メモリ 296,360 KB
実行使用メモリ 11,684 KB
最終ジャッジ日時 2024-11-18 18:42:31
合計ジャッジ時間 12,923 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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
0.upto(h - 4) do |i|
  s[i][w - 2] = true
  s[i][w - 1] = true
end
0.upto(w - 4) do |i|
  s[h - 2][i] = true
  s[h - 1][i] = true
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
    [[-1, 0], [-1, 1], [-1, 2], [0, -1], [0, 0], [0, 1], [0, 2], [0, 3], [1, -1], [1, 0], [1, 1], [1, 2], [1, 3], [2, -1], [2, 0], [2, 1], [2, 2], [2, 3], [3, 0], [3, 1], [3, 2]].each do |mv|
      my = mv[0] + i
      mx = mv[1] = j
      next if my < 0 || h <= my || mx < 0 || w <= mx
      next if my < 3 && mx < 3
      next if my >= h - 3 && mx >= w - 3
      -2.upto(0) do |dy|
        -2.upto(0) do |dx|
          ny = my + dy
          nx = mx + dx
          next if ny < 0 || h <= ny || nx < 0 || w <= nx
          g[i * w + j] << {ny * w + nx, 1}
        end
      end
    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
  # puts [cp // w, cp % w, cd]
  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