奇怪的游戏
测试数据来自 system/1940
描述
Blinker最近喜欢上一个奇怪的游戏。
这个游戏在一个 N x M 的棋盘上玩,每个格子有一个数。每次 Blinker 会选择两个相邻
的格子,并使这两个数都加上 1。
现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数,如果永远不能变成同
一个数则输出-1。
格式
输入格式
输入的第一行是一个整数T,表示输入数据有T轮游戏组成。
每轮游戏的第一行有两个整数N和M, 分别代表棋盘的行数和列数。
接下来有N行,每行 M个数。
输出格式
对于每个游戏输出最少能使游戏结束的次数,如果永远不能变成同一个数则输出-1。
样例1
样例输入1
3
2 2
1 2
2 3
3 3
1 2 3
2 3 4
4 3 2
10 10
16 12 9 13 16 12 10 14 12 19
12 7 4 8 13 13 5 14 7 17
13 16 4 7 13 13 9 11 6 15
10 9 3 0 9 8 9 10 9 16
12 11 12 6 8 5 14 9 11 19
12 5 4 5 6 5 12 6 7 16
12 8 3 12 7 6 11 6 8 18
13 13 5 10 9 12 10 5 10 18
11 7 8 8 10 13 13 11 10 17
15 12 17 15 10 10 15 17 12 17
样例输出1
2
-1
424
限制
对于30%的数据,保证 T<=10,1<=N,M<=8
对于100%的数据,保证 T<=10,1<=N,M<=40,所有数为正整数且小于1000000000
来源
SCOI 2012
数据为vijos原创,与SCOI 2012原始数据不同。