#4101. 钥匙之路

钥匙之路

题目名称:钥匙之路


【问题描述】

你被困在一个迷宫中,迷宫是一个 N × M 的矩阵,由以下几种字符组成:

  • 'S':起点(唯一)
  • 'E':终点(唯一)
  • 'K':钥匙(唯一,必须经过)
  • '.':空地(可以通行)
  • '#':墙壁(不可通行)

你每次可以向上下左右四个方向移动到相邻的格子。请判断:是否存在一条从 'S''E' 的路径,且这条路径必须经过 'K'


【输入格式】

第一行两个整数 N 和 M(1 ≤ N, M ≤ 1000),表示迷宫的行数和列数。 接下来 N 行,每行 M 个字符,构成迷宫地图。


【输出格式】

YES 如果存在一条合法路径(从 S 到 E,且路径中经过 K) NO 否则


🎯【输入样例】

6 7
S.#....
.#.###.
.#..#K.
.##.#.#
.#...E#
.......

🎯【输出样例】

YES