BOJ 2873ジェットコースター

https://www.acmicpc.net/problem/2873
1秒、256 MBメモリ
input :

R C (2 ≤ R, C ≤ 1000)

喜び(0<喜び<1000)

output :

出力はどのように移動するか(上はU、右はR、左はL、下はD)

条件:

ジェットコースターは一番左上の車両から、一番右下の車両から

に到着します

上、下、左、右の隣接セル

に移動
各

は1回アクセスできますが、未アクセスの部屋もあります.

各車両には、乗客がこの車両を通過するときに得られる楽しみを示す数字があります.ジェットコースターに乗っている人が得られる楽しみは、昔の楽しみの和

です.
これは長い戦いだった・・・
最初は奇数の場合、すべてのセルをチェックできることを確認してください.
問題が偶数の場合.最後の一格を出すだけの安易な考えを持っている.他の状況が発生したのを見て、後頭部が痛くなりました.
他の草を見て...道唐体が分からないので白俊の解答を見ました.大きな格子を小さな格子の草に変えるのが一番わかりやすいです.
それを実現すればいいのですが・・・
まずスタートとゴールに分けます.
始点から移動するものをfront変数に入れます.
終点までの移動経路は後に保存されます.
一番目.最小値が見つかったら.メッシュシェイプを値を含む行に縮小します.

front += (('R' * (m - 1) + 'D') + ('L' * (m - 1) + 'D')) * (x // 2)
back += (('D' + 'L' * (m - 1)) + ('D' + 'R' * (m - 1))) * ((n - x - 1) // 2)

始点から2行下に移動する方法を示します.
到着点から2行目に存在する点から到着点への移動方法を格納する.
では残りの移動は残りの2行で移動します.
このとき移動するパスにパターンが存在します.
始点の場合はDRURに移動し、2グリッド横に移動します.
0 -> 2 -> 4 ....
到着地点まで移動する場合は、RURDで同様に2マス横に移動します.
1 -> 3 -> 5 ...
また、この動作は行の位置を変えることはないので、他のことを考える必要はありません.
targetが前の行でも次の行でも、移動は上記の状況の影響を受けます.
最後に2*2の格子模様が現れたとき.
targetが0コラムに存在する場合、研究開発
targetがコラム1に存在する場合、DRに移動します.

    if y % 2 == 0:
        front += 'DRUR' * (y // 2) + 'RD'
        back = 'RURD' * ((m - y - 2) // 2) + back
    else:
        front += 'DRUR' * ((y - 1) // 2) + 'DR'
        back = 'RURD' * ((m - y - 1) // 2) + back

backの場合、最後の2行が残っている間に移動します./前に計算した2行ごとの移動より先に行うからです.
back=+backで計算する必要があります.
実は...『Baek Jun』は絵が一番いいです...
上の計算で一つ漏れていたので、もがいてしまいました...
そして除算に注意...これももがいた

import sys

n, m = map(int, sys.stdin.readline().split())
graph = []
for i in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))

ret = ''
front = ''
back = ''
if n % 2 == 1:
    ret += (('R' * (m - 1) + 'D') + ('L' * (m - 1) + 'D')) * (n // 2) + 'R' * (m - 1)
elif m % 2 == 1:
    ret += (('D' * (n - 1) + 'R') + ('U' * (n - 1) + 'R')) * ((n - 1) // 2) + 'D' * (n - 1)
else:
    score = 999
    x, y = -1, -1
    for i in range(0, n, 2):
        for j in range(1, m, 2):
            if score > graph[i][j]:
                x = i
                y = j
                score = graph[i][j]
    for i in range(1, n, 2):
        for j in range(0, m, 2):
            if score > graph[i][j]:
                x = i
                y = j
                score = graph[i][j]
    front += (('R' * (m - 1) + 'D') + ('L' * (m - 1) + 'D')) * (x // 2)
    back += (('D' + 'L' * (m - 1)) + ('D' + 'R' * (m - 1))) * ((n - x - 1) // 2)
    if y % 2 == 0:
        front += 'DRUR' * (y // 2) + 'RD'
        back = 'RURD' * ((m - y - 2) // 2) + back
    else:
        front += 'DRUR' * ((y - 1) // 2) + 'DR'
        back = 'RURD' * ((m - y - 1) // 2) + back
    ret = front + back
print(ret)