链接: https://cses.fi/problemset/task/1193

板块: Graph Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

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

输入

第一行输入包含两个整数 $n$ 和 $m$：地图的高度和宽度。

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

输出

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

如果存在路径，输出最短路径的长度，以及由字符 L（左）、R（右）、U（上）、D（下）组成的路径描述字符串。你可以输出任意合法解。

数据范围

$1 \le n,m \le 1000$

样例输入

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

样例输出

YES
9
LDDRRRRRU