{"problem":{"name":"[yLCPC2024] B. 找机厅","description":{"content":"给定一个 $n$ 行 $m$ 列的 $01$ 矩阵，记矩阵第 $i$ 行第 $j$ 列的格子是 $(i, j)$（$1 \\leq i \\leq n$，$1 \\leq j \\leq m$）。 你要从矩阵的左上角出发到达右下角。行走规则如下： - 如果你在格子 $(i, j)$，你下一步只能走到：$(i - 1, j)$、$(i + 1, j)$、$(i, j - 1)$、$(i, j + 1)$","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10234"},"statements":[{"statement_type":"Markdown","content":"给定一个 $n$ 行 $m$ 列的 $01$ 矩阵，记矩阵第 $i$ 行第 $j$ 列的格子是 $(i, j)$（$1 \\leq i \\leq n$，$1 \\leq j \\leq m$）。\n\n你要从矩阵的左上角出发到达右下角。行走规则如下：\n\n- 如果你在格子 $(i, j)$，你下一步只能走到：$(i - 1, j)$、$(i + 1, j)$、$(i, j - 1)$、$(i, j + 1)$ 四个格子的其中之一。\n- 任意时刻你不能走出这个矩阵，即你的位置 $(i, j)$ 必须时刻满足 $1 \\leq i \\leq n$，$1 \\leq j \\leq m$。\n- 如果你想从一个格子走到另一个格子，除了满足上述的要求外，还必须保证：这两个格子对应的数字不同。即：写着 $0$ 的格子只能走到写着 $1$ 的格子，反之亦然。\n\n你每走一步就需要花费一个单位的时间。你需要用最短的时间从 $(1, 1)$ 到达 $(n, m)$。除了给出最短时间外，你还必须给出一种可行的最短用时的行走方法。\n\n## Input\n\n**本题单个测试点内有多组测试数据**。第一行是一个正整数 $T$，表示数据组数。对每组数据：\n\n第一行是两个整数 $n, m$（$1 \\leq n, m \\leq 2 \\times 10^3$），表示矩阵的行数和列数。  \n接下来 $n$ 行，每行一个长度为 $m$ 的仅含字符 `0` `1` 的字符串，表示这个矩阵。\n\n数据保证每组数据内的 $n$ 之和、$m$ 之和均不超过 $2 \\times 10^3$。\n\n## Output\n\n对每组数据，输出一行或两行：\n\n如果从 $(1, 1)$ 无法到达 $(n, m)$，输出一行一个 $-1$ 表示无解。\n\n否则按如下规则输出：\n\n- 第一行输出一个整数 $t$，表示从左上角走到右下角的最短用时。\n- 第二行输出一个长度为 $t$ 的仅含字符 `L` `R` `U` `D` 的字符串 $s$，表示你给出的行走方法：\n  + 如果给出的行走方法第 $i$ 次移动是从 $(i, j)$ 走向 $(i - 1, j)$，则 $s_i = \\texttt{U}$。\n  + 如果给出的行走方法第 $i$ 次移动是从 $(i, j)$ 走向 $(i + 1, j)$，则 $s_i = \\texttt{D}$。\n  + 如果给出的行走方法第 $i$ 次移动是从 $(i, j)$ 走向 $(i, j-1)$，则 $s_i = \\texttt{L}$。\n  + 如果给出的行走方法第 $i$ 次移动是从 $(i, j)$ 走向 $(i, j + 1)$，则 $s_i = \\texttt{R}$。\n\n你第二行输出的字符串长度必须恰好为第一行给出的最短用时 $t$。如果有多种方案符合要求，你可以输出任意一种。\n\n[samples]\n\n## Background\n\n扶苏正在出发去打 mai！\n\n但是商场内部实在太复杂了，她在里面迷路了。已经在地铁站迷路过一次的扶苏看着商场的地图实在是不懂怎么走，你能帮帮她吗？","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10234","tags":["洛谷原创","Special Judge","广度优先搜索 BFS","洛谷月赛"],"sample_group":[["2\n2 2\n01\n11\n2 2\n01\n10","-1\n2\nRD"]],"created_at":"2026-03-03 11:09:25"}}