首页 > 代码库 > BZOJ 2756: [SCOI2012]奇怪的游戏

BZOJ 2756: [SCOI2012]奇怪的游戏

2756: [SCOI2012]奇怪的游戏

Time Limit: 40 Sec  Memory Limit: 128 MB
Submit: 3410  Solved: 941
[Submit][Status][Discuss]

Description

Blinker最近喜欢上一个奇怪的游戏。 
这个游戏在一个 N*M 的棋盘上玩,每个格子有一个数。每次 Blinker 会选择两个相邻
的格子,并使这两个数都加上 1。 
现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数,如果永远不能变成同
一个数则输出-1。 

Input

输入的第一行是一个整数T,表示输入数据有T轮游戏组成。 
每轮游戏的第一行有两个整数N和M, 分别代表棋盘的行数和列数。 
接下来有N行,每行 M个数。 

Output


  对于每个游戏输出最少能使游戏结束的次数,如果永远不能变成同一个数则输出-1。

Sample Input

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

Sample Output

2
-1

HINT

 

【数据范围】 

    对于30%的数据,保证  T<=10,1<=N,M<=8 

对于100%的数据,保证  T<=10,1<=N,M<=40,所有数为正整数且小于1000000000 

 

 

Source

 
[Submit][Status][Discuss]

 

二分答案 + 网络流判断

 

不难看出,对棋盘进行黑白染色之后,每次相加都会使得相邻的一黑一白两个格子同时+1,。

先对所有黑白格子进行统计,处理出$cnt0$,$cnt1$分别代表黑、白格子个数,处理出$sum0$,$sum1$分别代表黑、白格子权值和。

分类讨论如下:

如果$cnt0=cnt1$

  如果$sum0\not = sum1$

 

BZOJ 2756: [SCOI2012]奇怪的游戏