31 - 二维迷宫

通过次数

113

提交次数

301

时间限制 : 1 秒
内存限制 : 128 MB

给你一个 nm 列 的迷宫,迷宫的每一个格子可能是是路,也有可能是墙。我们只能走到路上而不能走到墙上。

现在你需要判断是否存在可行的方案,从二维迷宫中左上角的格子走到右下角。

说明:如果你当前在二维迷宫中的某一个点,你能够走到的点仅仅只有当前点上下左右四个点中在迷宫中的可走的路。

输入

输入的第一行包含两个整数 nm ,分别表示迷宫的行数和列数。

接下来 n 行,每行包含一个长度为 m 的字符串,用于表示这个二维迷宫。

对于二维迷宫中的每一个点,我们用“.”表示可走的路,用“#”表示不可走的墙。

数据保证左上角的起点(即第1行第1个点)和右下角的终点(即第n行第m个点)都是可走的路。

输出

如果从左上角到右下角存在可行的路,输出“YES”;否则,输出“NO”。

样例

输入

4 5
..###
#....
####.
####.

输出

YES

输入

4 5
.....
.####
...#.
###..

输出

NO

提示

【样例解释】

对于第1组样例,我们可以按照:右下右右有下下 的方式从起点到达终点;

对于第2组样例,我们没有办法从左上角到达右下角。

【数据规模】

50% 的数据,满足 1≤n,m≤100;

100%的数据,满足 1≤n,m≤1000。