迷宫
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给定一个 \mathrm{n \times m} 的迷宫,迷宫由 "#" 与"." 两种字符组成。其中 "#" 代表障碍物,"." 表示空地。迷宫中还有一个起点 "S" 和一个终点 "E" ,它们都可以视为空地。

由于近期迷宫发生了塌方,导致起点和终点之间可能并不连通。幸运的是,你拥有一种超能力——在迷宫中移动时(移动方向为上、下、左、右四个方向之一),可以在当前位置朝任一方向(上、下、左、右四个方向之一)释放激光。激光能够清除该方向上所有的障碍物,并且这种超能力至多只能使用一次。

现在,你需要判断是否能利用这种超能力成功从起点到达终点。

输入描述:

第一行给定两个整数 \mathrm{n,m}(\mathrm{2 \le n,m \le 1000}) ,分别表示迷宫的行数和列数。

下面 \mathrm{n} 行,每行 \mathrm{m} 个字符,描述迷宫的具体布局。字符只包含 "#"、"."、"S" 和 "E",并且起点与终点有且仅有一个。

输出描述:

能够到达终点输出 \mathrm{YES} ;否则输出 \mathrm{NO}
示例1

输入

复制
4 5
.####
S####
.####
.E###

输出

复制
YES
示例2

输入

复制
4 5
..###
S####
#####
##.E#

输出

复制
YES

说明

显然可以从起点出发,到达\mathrm{(1,2)}处并向下方使用超能力,此时可以从起点到达终点。
示例3

输入

复制
4 5
..###
S####
#####
###E#

输出

复制
NO