#393. 迷宫之判定

    ID: 393 传统题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>搜索深度优先搜索广度优先搜索网格图CF信奥C++4.1-AC课程

迷宫之判定

题目描述

我是子睿,我要走!迷!!宫!!! 一个迷宫由 nn 行 mm 列的格子组成。部分格子是空地,可以通过;部分格子是障碍物,不能通过。

给定迷宫,请判断能否从左上角 (1,1)(1,1) 出发,经过若干次移动到达右下角 (n,m)(n,m)。

每次只能向上、下、左、右相邻的格子移动一格,不能移出迷宫,也不能进入障碍物格子。

输入格式

第一行包含两个整数 n,mn,m,分别表示迷宫的行数和列数。

接下来 nn 行,每行包含 mm 个字符,表示迷宫的布局:

  • 0 表示空地,可以通行;
  • 1 表示障碍物,不能通行。

保证左上角和右下角均为空地,即两个位置的字符都是 0。

输出格式

输出一行:如果能够到达右下角,输出 YES;否则输出 NO。

注意: 输出大写英文字母,不包含引号。

数据范围

1≤n,m≤401\le n,m\le 40。

样例

5 5
00111
10000
10101
10101
10100
YES

样例说明

可以从 (1,1)(1,1) 出发,沿空地逐步移动到右下角。不能沿对角线移动。