Monsters

题目描述

你和一些怪物在一个迷宫里。当你向某个方向走一步时，每个怪物也可能同时走一步。你的目标是在从未与怪物同处一个格子的情况下到达边界格之一。\n你的任务是判断你的目标是否可行，如果可行，输出一条你可以遵循的路径。你的计划必须在任何情况下都可行；即使怪物事先知道你的路径。

输入格式

第一行包含两个整数 n 和 m：地图的高度和宽度。\n随后有 n 行每行 m 个字符描述地图。每个字符是 .（地面），#（墙），A（起点），或 M（怪物）。输入中恰好有一个 A。

输出格式

首先如果你的目标可行则输出 "YES"，否则输出 "NO"。\n如果你的目标可行，还要输出一个有效路径的示例（路径长度以及使用字符 D、U、L 和 R 描述的路径）。只要路径长度不超过 $n \cdot m$ 步，你可以输出任意路径。

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

YES
5
RRDDR

提示

$1 \le n,m \le 1000$

标签: CSES1194|图论

来源

CSES1194|图论