You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1193 题。

题目描述

给定一个迷宫的地图，你的任务是从起点找到到终点的路径。你可以向左、向右、向上和向下走动。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示迷宫的高度和宽度。

接下来的 $n$ 行每行有 $m$ 个字符，描述迷宫的内容。每个字符要么是 .（表示地板），要么是 #（表示墙壁），A（表示起点），或 B（表示终点）。输入中恰好有一个 A 和一个 B。

输出格式

首先，如果有路径存在，输出 YES，否则输出 NO。

如果有路径，接着输出最短路径的长度，并且输出路径的描述，路径由字符 L（向左）、R（向右）、U（向上）和 D（向下）组成。你可以输出任何一个有效的路径。

样例

5 8
########
#.A#...#
#.##.#B#
#......#
########

YES
9
LDDRRRRRU

说明/提示

$1\le n, m \le 1000$。