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

板块: Graph Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

你和若干怪物身处一个迷宫中。在迷宫中向某个方向迈出一步时，每个怪物也可能同时迈出一步。你的目标是在不与任何怪物处于同一方格的前提下，到达某个边界方格。

你的任务是判断目标是否可行，如果可行，输出一条你可以遵循的路径。你的方案必须在任何情况下都成立；即便怪物事先知道你的路径。

输入

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

之后有 $n$ 行，每行 $m$ 个字符描述地图。每个字符是 .（地板）、#（墙）、A（起点）或 M（怪物）。输入中恰好有一个 A。

输出

如果目标可行，先输出 "YES"，否则输出 "NO"。

如果目标可行，还需输出一条合法路径的示例（路径长度及其用字符 D、U、L、R 描述的内容）。你可以输出任意路径，只要其长度不超过 $n \cdot m$ 步。

数据范围

$1 \le n,m \le 1000$

样例输入

5 8
########
#M..A..#
#.#.M#.#
#M#..#..
#.######

样例输出

YES
5
RRDDR