結果

問題 No.2412 YOU Grow Bigger!
ユーザー tomeruntomerun
提出日時 2023-08-11 23:20:19
言語 Crystal
(1.11.2)
結果
WA  
実行時間 -
コード長 1,956 bytes
コンパイル時間 14,095 ms
コンパイル使用メモリ 294,948 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-29 14:31:33
合計ジャッジ時間 14,658 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 5 ms
5,376 KB
testcase_10 AC 4 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 5 ms
5,376 KB
testcase_14 AC 4 ms
5,376 KB
testcase_15 AC 4 ms
5,376 KB
testcase_16 AC 5 ms
5,376 KB
testcase_17 AC 4 ms
5,376 KB
testcase_18 AC 5 ms
5,376 KB
testcase_19 AC 4 ms
5,376 KB
testcase_20 AC 3 ms
5,376 KB
testcase_21 AC 4 ms
5,376 KB
testcase_22 AC 5 ms
5,376 KB
testcase_23 AC 4 ms
5,376 KB
testcase_24 AC 5 ms
5,376 KB
testcase_25 WA -
testcase_26 AC 4 ms
5,376 KB
testcase_27 AC 3 ms
5,376 KB
testcase_28 AC 4 ms
5,376 KB
testcase_29 AC 5 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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
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
    -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