#941. 土拨鼠绕迷宫
土拨鼠绕迷宫
故事背景
土拨鼠稀里糊涂地走进了一个 的且仅由0和1组成的矩阵迷宫的左上角,这时,土拨鼠身后的门突然封闭起来了。
这时,一艘外星飞船从天而降,对土拨鼠说:“现在你已经到了矩阵迷宫的左上角,你需要在这个矩阵中蛇形的绕圈寻找所有的1。最后以你走过的路径展开,得到一个由01组成的二进制序列。接下来你需要将这个二进制序列转为十进制。如果这个十进制数能被你刚所找到的1的个数整除,则你可以离开迷宫。否则就永远别想出去了。”
现在外星飞船从迷宫上空拍下迷宫的全貌并发给你,请你编程计算一下土拨鼠能否顺利逃出。
题目描述
给定一个 的正方形01矩阵,请你按照蛇形将矩阵变为一个二进制数并转为十进制。同时你还要找到矩阵中1的个数。如果十进制数能整除1的个数,则输出y
,否则输出n
.
将以下矩阵展开
0 1 0 1
1 0 1 1
0 0 1 0
1 0 0 1
得到二进制数0101110100101001
转为十进制是23849
矩阵中有8
个1
23849
不能整除8
所以这个矩阵土拨鼠不能逃出
输入格式
第一行包含一个整数 , 表示共有多少组测试数据
第二行包含1个整数 ,表示矩阵的高和宽。
接下来输入一个矩阵(带空格),且矩阵中只有0和1。
输出格式
输出t行数据, 判断土拨鼠能否顺利逃出这个矩阵。能则输出y
,不能则输出n
。
样例
1
4
0 1 0 1
1 0 1 1
0 0 1 0
1 0 0 1
n
23849 % 8 = 1
2
2
1 1
0 0
4
0 1 0 1
1 0 1 1
0 0 1 0
1 0 0 1
y
n
12 % 2 = 0
23849 % 8 = 1
提示
蛇形展开: