この問題は中国郵便配達人問題と呼ばれる問題になっています。中国郵便配達人問題は以下のような問題です。

\(G\) を連結な無向グラフとし、\(G\) の各辺には距離が割り当てられている。このとき、\(G\) の辺をすべて通るような閉路のうち、距離の合計が最小になるものを求めよ。

この問題は以下のように解くことができます。

• \(G\) の頂点のうち次数が奇数であるような頂点集合を \(S\) とする。 \(S\) の大きさは必ず偶数になる。
• \(S\) の頂点同士を全て過不足なくマッチングさせ、マッチングした頂点同士に新たに辺を繋ぐ。
• 全ての頂点の次数が偶数となったグラフ \(G\) に対し、オイラー路を求める。

ただし、この問題ではステージ間の移動は通路でしかできないため、マッチングした頂点同士に新たに繋がれる辺の長さはマンハッタン距離と一致します。

さらに、繋いだ辺の長さの総和だけオイラー路の長さも長くなるため、このマッチングは重みの総和が最小になるようにする必要があります。

次数が奇数であるような頂点の集合は \(S=\lbrace (0,1),(0,2),\ldots,(0,W-1),(1,0),(2,0),\ldots,(H-1,0),(1,W),(2,W),\ldots,(H-1,W),(H,1),(H,2),\ldots,(H,W-1) \rbrace\) （それぞれの要素を順に \(S_1,S_2,\ldots,S_{|S|}\) とする）であることを踏まえると、 \(k=1,2,\ldots,|S|/2\) に対し頂点 \(S_{2k-1}\) と頂点 \(S_{2k}\) をマッチングさせれば良いことが分かります。直感的には、次数が奇数である頂点を順に時計回りに近い順にマッチングさせていけば良いです。

あとは新たに辺を繋いだ頂点のオイラー路を求め、そこから経路を復元すれば良いです。

実装例(Python3)

import collections


def find_eulerian_path(g):
    n = len(g)
    adj = [collections.Counter(neighbors) for neighbors in g]

    path = []
    st = [0]

    while st:
        v = st[-1]
        if adj[v]:
            u = next(iter(adj[v]))

            adj[v][u] -= 1
            if adj[v][u] == 0:
                del adj[v][u]

            adj[u][v] -= 1
            if adj[u][v] == 0:
                del adj[u][v]

            st.append(u)
        else:
            path.append(st.pop())

    return path[::-1]


h, w = map(int, input().split())
h, w = h + 1, w + 1
n = h * w
g = [[] for _ in range(n)]


def f(x, y):
    return x * w + y


for x in range(h):
    for y in range(w):
        if x + 1 != h:
            i, j = f(x, y), f(x + 1, y)
            g[i].append(j)
            g[j].append(i)
        if y + 1 != w:
            i, j = f(x, y), f(x, y + 1)
            g[i].append(j)
            g[j].append(i)
c = []
for i in range(1, w - 1):
    c.append(f(0, i))
for j in range(1, h - 1):
    c.append(f(j, w - 1))
for i in reversed(range(1, w - 1)):
    c.append(f(h - 1, i))
for j in reversed(range(1, h - 1)):
    c.append(f(j, 0))


for i in range(0, len(c), 2):
    g[c[i]].append(c[i + 1])
    g[c[i + 1]].append(c[i])
p = find_eulerian_path(g)

s = []
for i in range(1, len(p)):
    r0, c0 = p[i - 1] // w, p[i - 1] % w
    r1, c1 = p[i] // w, p[i] % w
    s += ["D" * max(0, r1 - r0)]
    s += ["U" * max(0, r0 - r1)]
    s += ["R" * max(0, c1 - c0)]
    s += ["L" * max(0, c0 - c1)]
print("".join(s))