2663. Mike下棋

【题目描述】

Mike爱好下棋，从小就和路边的老爷爷们一起玩。而有一天，Mike正在观察棋盘，突然发现了一个问题：Mike的棋子全部连在一起了。

(Mike原创，红先绿后，有兴趣的同学可以玩玩）

Mike觉得不妙，一位经验丰富的长者曾说过，布局应该张弛有道，不宜太密。Mike决定用这样一个方法衡量自己的棋子有多么密。

Mike找到了许多线，并且在自己的每个棋子上打上了上下左右四个方向的眼，Mike可以让线从棋子的一个孔穿进去，并从另一个孔穿出去。每个棋子中央空间有限，只能允许一根线穿过这个棋子。如果Mike能够把一条线穿成一个环，打上死结，那是再好不过的了。否则，Mike需要把这根线两端都从与棋盘边缘相连的孔伸出来固定在棋盘外柱子上。

所以，线只能在相邻的棋子相对的孔之间连接，或者从棋盘边缘连出棋盘。如果一条线从棋盘四角的一个棋子连入又连出，Mike认为这不优美，因此他一定不会这样做。下面是一个不合法的连接方式（棋盘是2*2的，其中-|表示线，连出棋盘的线接着柱子，含义看下面输入格式）

 |

-1 0

 0 0

Mike希望用尽量少的不成环的线，让所有棋子的中央空间全部占满，这个值Mike认为就是他布局的拥挤度。

请你告诉Mike这个最小的拥挤度。

【输入格式】

第一行两个整数n,m，表示棋盘的行数和列数。

下面n行，每行m个数字，1表示这个位置是Mike的棋子，0表示这是个空格子，或者是对手的棋子。

【输出格式】

一行一个整数，如果不存在这样的方案，请输出-1，否则输出最少不成环的线数量。

每条不成环的线的两端都要直接连出棋盘！！！

【样例输入】

6 6
1 1 1 1 1 1
1 0 0 1 0 1
1 1 1 1 0 1
1 0 1 1 1 1
1 0 1 0 0 1
1 1 1 1 1 1

【样例输出】

2

下面是一种可行解，其中-|表示线，连出棋盘的线接着柱子
         |
 1-1-1-1 1-1
 |     |   |
 1 0 0 1 0 1
 |     |   |
 1-1-1-1 0 1
           |
-1 0 1-1-1-1
 |   |
 1 0 1 0 0 1-
 |   |     |
 1-1 1-1-1-1
   |

【提示】

数据范围n,m<=50

对于前10%的数据，n,m<=5

对于前60%的数据，n,m<=12

【来源】

Mike