Problem C. 金字塔探险II

时间限制：3s

空间限制：256MB

题目描述

小明刚进入第一个房间就感觉自己中了陷阱，房间被突然生成的隔板分成了\(n*m\)个小房间，小明被困在了房间\((1,1)\)中。但是很幸运，建造者给入侵者留下了一线生机。小明找到了一张地图和一双特制的鞋。地图上标出了每个房间的权值，而特制的鞋可以帮助小明传送到行号和列号相乘等于该房间权值的任意房间，更具体的来说：

用\((r,c)\)代表第 \(r\) 行第 \(c\) 列的房间，\(w[r][j]\) 代表房间 \((r,c)\) 的权值；

如果小明当前在房间 \((i,j)\) 内，那么小明可以传送到任意满足 \(a * b = w[i][j]\) 的 \((a,b)\) 房间，只要 \((a,b)\) 没有超出大房间。

比如说，假设当前小明所处房间的权值为 \(10\), 房间大小为 \(5*5\)；那么小明可以传送到 \((2,5)\) 和 \((5,2)\) ，因为 \(2*5=10\);但是不能传送到 \((1,10)\) 和 \((10,1)\)，因为这两个房间超出了房间大小限制。

小明只有到达房间 \((n,m)\)才能出去，现在请你判断小明能否逃出这个房间。

输入格式

第一行一个整数\(T\)，代表测试数据组数.

接下来每一组的输入格式如下：

第一行两个整数 \(n,m\),代表房间大小为 \(n\) 行 \(m\) 列，用空格隔开；

接下来 \(n\) 行每行 \(m\) 个数，用空格隔开；其中第 \(i\) 行第 \(j\) 列的数代表房间 \((i,j)\) 的权值。

输出格式

对于每一组数据输出一行结果，如果能到达房间 \((n,m)\)，则输出 "yes"，否则输出"no"。

输入样例1

2
1 3
2 3 1
2 2
2 6
1 4

输出样例1

yes
no

样例1解释

第一组路线如下：\((1,1)\)（权值为2）\(\rightarrow\) \((1,2)\)（权值为3）\(\rightarrow\) \((1,3)\)。

第二组无论怎么传送，都无法出去；因为要不就是在 \((1,1)\) 和 \((2,1)\) 之前相互传送，要不就是在 \((1,2)\) 无法传送到任何房间。

输入样例2

1
3 4
3 10 8 14
1 11 12 12
6 2 3 9

输出样例2

yes

输入样例3

见room3.in

输出样例3

见room3.out

输入样例4

见room4.in

输出样例4

见room4.out

数据范围与限制

测试点编号	约定	测试点分值
\(1 \sim 4\)	\(w[i][j] > n*m\) 或者 \(w[1][1] = n*m\)	每个测试点5分
\(5 \sim 6\)	\(n = 1\) 或者 \(m=1\)	每个测试点5分
\(7 \sim 8\)	\(1 \le n,m \le 3\)	每个测试点5分
\(9 \sim 12\)	\(1 \le n,m \le 100\)	每个测试点5分
\(13 \sim 20\)	无特殊约定	每个测试点5分

对于所有测试点，\(1 \le T \le 5\),\(1 \le n,m \le 1000\),\(1 \le w[i][j] \le 10^6\).