結果

問題 No.2411 Reverse Directions
ユーザー tomeruntomerun
提出日時 2023-08-11 22:15:58
言語 Crystal
(1.11.2)
結果
WA  
実行時間 -
コード長 1,752 bytes
コンパイル時間 16,390 ms
コンパイル使用メモリ 295,260 KB
実行使用メモリ 18,420 KB
最終ジャッジ日時 2024-11-18 16:44:07
合計ジャッジ時間 16,706 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

INF = 1 << 29
DR  = [1, 0, -1, 0]
DC  = [0, 1, 0, -1]
h, w, k, l, r = read_line.split.map(&.to_i)
if h - 1 + w - 1 > k || (h + w + k) % 2 != 0 || (r - l + 1) % 2 != 0
  puts "No"
  exit
end
l -= 1
r -= 1
s = Array.new(h) { [true] + read_line.chars.map { |ch| ch == '#' } + [true] }
s.unshift([true] * (w + 2))
s << [true] * (w + 2)
dist0, prev0 = bfs(s, 1, 1)
dist1, prev1 = bfs(s, h, w)
py = -1
px = -1
1.upto(h) do |y|
  1.upto(w) do |x|
    d0 = dist0[y][x]
    d1 = dist1[y][x]
    next if (l + d0) % 2 != 0
    next if l < d0
    next if (k - 1 - r + d1) % 2 != 0
    next if k - 1 - r < d1
    if !s[y - 1][x] && !s[y + 1][x] || !s[y][x - 1] && !s[y][x + 1]
      py = y
      px = x
      puts [py, px]
    end
  end
end
if py == -1
  puts "No"
  exit
end
prefix = [] of Int32
cy = py
cx = px
while cy != 1 || cx != 1
  dir = prev0[cy][cx]
  prefix << dir
  cy -= DR[dir]
  cx -= DC[dir]
end
prefix.reverse!
suffix = [] of Int32
cy = py
cx = px
while cy != h || cx != w
  dir = prev1[cy][cx]
  suffix << (dir ^ 2)
  cy -= DR[dir]
  cx -= DC[dir]
end
ans = prefix
if !s[py - 1][px] && !s[py + 1][px]
  ans += [0, 2] * ((k - prefix.size - suffix.size) // 2)
else
  ans += [1, 3] * ((k - prefix.size - suffix.size) // 2)
end
ans += suffix
puts ans.map { |d| "DRUL"[d] }.join

def bfs(s, y, x)
  dist = Array.new(s.size) { Array.new(s[0].size, INF) }
  prev = Array.new(s.size) { Array.new(s[0].size, 5) }
  dist[y][x] = 0
  q = [{y, x}]
  qi = 0
  while qi < q.size
    cy, cx = q[qi]
    4.times do |dir|
      ny = cy + DR[dir]
      nx = cx + DC[dir]
      if !s[ny][nx] && dist[ny][nx] == INF
        q << {ny, nx}
        dist[ny][nx] = dist[cy][cx] + 1
        prev[ny][nx] = dir
      end
    end
    qi += 1
  end
  return {dist, prev}
end
0