好奇特的题。
考虑显式建图，那么这是一个 \(9\) 个结点，\(12\) 条边的图，需要找到一条回路使得第 \(i\) 个点被经过 \(a_i\) 次。
首先会有一个基本思路：先求出每条边经过的次数，然后每条边复制这么多次即可直接构造欧拉回路。其中每条边经过次数的限制就是，每个点连出去的边，经过次数之和等于 \(2 \times a_i\)，并且去掉没经过的边，图仍然连通。
考虑直接暴力枚举图的一棵生成树，钦定这些边至少被经过 \(1\) 次，然后在这个二分图上跑最大流，判断最大流是否为 \(\sum a_i\) 即可得知是否合法。
还有一种做法是，列出 \(9\) 个 \(12\) 元一次方程组，暴力枚举自由元的值判断。
code
// Problem: H - Eat Them All
// Contest: AtCoder - KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227)
// URL: https://atcoder.jp/contests/abc227/tasks/abc227_h
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
int a[99], b[99], head[99], len, S, T, ntot, fa[99], id[99];
struct edge {
int to, next, cap, flow;
} edges[9999];
inline void add_edge(int u, int v, int c, int f) {
edges[++len].to = v;
edges[len].next = head[u];
edges[len].cap = c;
edges[len].flow = f;
head[u] = len;
}
struct Dinic {
int d[99], cur[99];
bool vis[99];
inline void add(int u, int v, int c) {
add_edge(u, v, c, 0);
add_edge(v, u, 0, 0);
}
inline bool bfs() {
queue<int> q;
for (int i = 0; i <= ntot; ++i) {
vis[i] = 0;
d[i] = -1;
}
q.push(S);
vis[S] = 1;
d[S] = 0;
while (q.size()) {
int u = q.front();
q.pop();
for (int i = head[u]; i; i = edges[i].next) {
edge &e = edges[i];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = 1;
d[e.to] = d[u] + 1;
q.push(e.to);
}
}
}
return vis[T];
}
int dfs(int u, int a) {
if (u == T || !a) {
return a;
}
int flow = 0, f;
for (int &i = cur[u]; i; i = edges[i].next) {
edge &e = edges[i];
if (d[e.to] == d[u] + 1 && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
e.flow += f;
edges[i ^ 1].flow -= f;
flow += f;
a -= f;
if (!a) {
break;
}
}
}
return flow;
}
inline int solve() {
int flow = 0;
while (bfs()) {
for (int i = 0; i <= ntot; ++i) {
cur[i] = head[i];
}
flow += dfs(S, inf);
}
return flow;
}
} solver;
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
fa[x] = y;
return 1;
} else {
return 0;
}
}
int p[9999], tot;
vector<pii> G[99];
bool vis[9999];
void dfs(int u) {
for (pii p : G[u]) {
int v = p.fst, id = p.scd;
if (!vis[id]) {
vis[id] = 1;
dfs(v);
}
}
p[++tot] = u;
}
void solve() {
int s0 = 0, s1 = 0;
for (int i = 0; i < 3; ++i) {
for (int j = 0, x; j < 3; ++j) {
scanf("%d", &x);
a[i * 3 + j] = x * 2;
if ((i + j) & 1) {
s1 += a[i * 3 + j];
} else {
s0 += a[i * 3 + j];
}
}
}
if (s0 != s1) {
puts("NO");
return;
}
vector<pii> E;
E.pb(0, 1);
E.pb(1, 2);
E.pb(3, 4);
E.pb(4, 5);
E.pb(6, 7);
E.pb(7, 8);
E.pb(0, 3);
E.pb(3, 6);
E.pb(1, 4);
E.pb(4, 7);
E.pb(2, 5);
E.pb(5, 8);
for (int S = 1; S < (1 << 12); ++S) {
if (__builtin_popcount(S) != 8) {
continue;
}
for (int i = 0; i < 9; ++i) {
fa[i] = i;
b[i] = a[i];
vector<pii>().swap(G[i]);
}
bool flag = 0;
for (int i = 0; i < 12; ++i) {
if ((~S) & (1 << i)) {
continue;
}
if (!merge(E[i].fst, E[i].scd)) {
flag = 1;
break;
}
--b[E[i].fst];
--b[E[i].scd];
}
for (int i = 0; i < 9; ++i) {
if (b[i] < 0) {
flag = 1;
break;
}
}
if (flag) {
continue;
}
len = 1;
mems(head, 0);
ntot = 8;
::S = ++ntot;
T = ++ntot;
for (int i = 0; i < 12; ++i) {
int u = E[i].fst, v = E[i].scd;
if (u & 1) {
solver.add(v, u, inf);
} else {
solver.add(u, v, inf);
}
id[i] = len - 1;
}
for (int i = 0; i < 9; ++i) {
if (i & 1) {
solver.add(i, T, b[i]);
} else {
solver.add(::S, i, b[i]);
}
}
int flow = solver.solve();
if (flow + 8 != s0) {
continue;
}
mems(vis, 0);
int tt = 0;
for (int i = 0; i < 12; ++i) {
int k = ((S >> i) & 1) + edges[id[i]].flow, u = E[i].fst, v = E[i].scd;
for (int j = 0; j < k; ++j) {
G[u].pb(v, ++tt);
G[v].pb(u, tt);
}
}
dfs(0);
reverse(p + 1, p + tot + 1);
for (int i = 1; i < tot; ++i) {
if (p[i + 1] == p[i] + 1) {
putchar('R');
} else if (p[i + 1] == p[i] - 1) {
putchar('L');
} else if (p[i + 1] == p[i] + 3) {
putchar('D');
} else {
putchar('U');
}
}
return;
}
puts("NO");
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}