问题 3844 --迷宫判断

3844: 迷宫判断

时间限制: 3 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

小明最近沉迷与一个游戏,但是他在玩游戏中经常遇到各种各样的迷宫,其中既有走得通的迷宫也有走不通的迷宫。

小明懒得费这个力,想让你帮忙写一个程序帮他一劳永逸地解出所有的迷宫。

输入

第一行输入一个正整数n,代表待求解的迷宫的数量。

其后n组数据,每组数据输入一个数m,代表迷宫的长度和宽度。

其后输入m行,m列的一个矩阵,其中0代表此格有障碍,不能通行,1代表可以通过。

数据保证最左上角和最右下角的格子不会有障碍。

迷宫不会大于30x30。

输出

判断每个迷宫是否能从左上角的起点走到右下角的终点,每个迷宫输出“YES”或“NO”代表这个迷宫是否可以走通。

样例输入

2
3
1 1 0
0 1 1
0 0 1
4
1 1 0 1
0 0 1 1
1 1 0 1
1 1 0 1

样例输出

YES
NO

来源

 

[提交][状态]