3004: 无尽拼图

时间限制:1000 ms 内存限制:128 MB
上传者:
提交:19 通过:5

题目描述

彩虹岛人民世世代代守护着一块无边无垠的无尽拼图,人们坚信是这块完整的拼图庇护着整座彩虹岛。无尽拼图是由一些数字组成的,处在第$i$行第$j$列的拼图上的数字恰好为$i + j - 1$。下图为拼图的部分示意图。


邪恶的大魔王为了破坏彩虹岛的和平,他将无尽拼图打碎成了无数碎片,每一个碎片仍然是一个矩形。为了防止有人将拼图复原,大魔王将碎片上的一些数字抹去(抹去的部分数字用$0$表示),并且混入了一些伪造的拼图。然而这并不能阻挡彩虹岛人民复原拼图的决心,他们想请你帮忙判断一些拼图碎片是否有可能是真正的无尽拼图碎片(若碎片存在一种填补被抹去数字的方案使其成为原来无尽拼图的一部分,就认为它有可能是真正的无尽拼图碎片)。

输入格式

输入第一行为一个整数$T(T \leq 150)$,表示一共有$T$组测试数据。
对于每组测试数据:
第一行是两个整数$n$、$m(1 \leq n, m \leq 1000)$,表示碎片的行、列数。
接下来有$n$行,每行$m$个数字,数字之间用空格隔开,表示拼图碎片(数字保证不大于$10^8$,其中正数表示碎片上的数字,$0$表示此处数字被抹去)。

输出格式

对于每组测试数据:若有可能是真正的无尽拼图碎片,输出“YES”;否则,输出“NO”。

输入样例 复制

2
3 3
4 0 6
0 6 0
0 0 0
3 4
0 0 0 0
0 0 0 0
3 4 0 7

输出样例 复制

YES
NO

数据范围与提示