题目描述

有一个 n×n 的迷宫方格，方格内 0 表示可以通行，1 表示是障碍物不能通行。人在左上角 (1, 1) 位置，可以向当前位置的上、下、左、右四个方向行走，问能否走到右下角宝箱位置 (n, n)。测试数据保证起点和终点均为 0，走的过程不能走出迷宫。

输入格式

输入第一行为 n（2 ≤ n ≤ 10），表示 n×n 的方格；接下来 n 行，每行 n 个整数（0 或 1），整数间用空格隔开。

输出格式

如果可以走到终点，输出 YES，否则输出 NO。

样例

3
0 0 1
1 0 0
0 1 0

YES

说明/提示

使用深度优先搜索，从 (1,1) 出发，沿上下左右四个方向搜索，标记已访问过的格子避免重复；到达 (n,n) 即可判定为 YES。