Labyrinth

题目描述

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

输入格式

第一行输入有两个整数 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$

标签: CSES1193|图论

来源

CSES1193|图论