Problem1123--#2321. 「清华集训 2017」无限之环

1123: #2321. 「清华集训 2017」无限之环

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

曾经有一款流行的游戏,叫做 Infinity Loop,先来简单的介绍一下这个游戏:

游戏在一个 n×mn \times mn×m 的网格状棋盘上进行,其中有些小方格中会有水管,水管可能在方格某些方向的边界的中点有接口,所有水管的粗细都相同,所以如果两个相邻方格的公共边界的中点都有接头,那么可以看作这两个接头互相连接。水管有以下 151515 种形状:

Screen Shot 2017-12-04 at 18.13.48.png Screen Shot 2017-12-04 at 18.13.55.png

游戏开始时,棋盘中水管可能存在漏水的地方。

形式化地:如果存在某个接头,没有和其它接头相连接,那么它就是一个漏水的地方。

玩家可以进行一种操作:选定一个含有非直线型水管的方格,将其中的水管绕方格中心顺时针或逆时针旋转 909090 度。

直线型水管是指左图里中间一行的两种水管。

现给出一个初始局面,请问最少进行多少次操作可以使棋盘上不存在漏水的地方。

输入格式

第一行两个正整数 n,mn,mn,m,代表网格的大小。

接下来 nnn 行每行 mmm 个数,每个数是 [0,15][0,15][0,15] 中的一个,你可以将其看作一个 444 位的二进制数,从低到高每一位分别代表初始局面中这个格子上、右、下、左方向上是否有 水管接头。

特别地,如果这个数是 000,则意味着这个位置没有水管。

比如 3(0011(2))3(0011_{(2)})3(0011(2)) 代表上和右有接头,也就是一个 L 型,而 12(1100(2))12(1100_{(2)})12(1100(2)) 代表下和左有接头,也就是将 L 型旋转 180180180 度。

输出格式

输出共一行,表示最少操作次数。如果无法达成目标,输出 −1-11.

样例

样例输入 1

2 3
3 14 12
3 11 12

样例输出 1

2

样例输入 2

3 2 
1 8 
5 10 
2 4

样例输出 2

-1

样例输入 3

3 3
9 11 3
13 15 7 
12 14 6

样例输出 3

16

数据范围与提示

测试点编号n×mn\times mn×m 的范围特殊约定
1n×m≤16n\times m \le 16n×m16 无特殊要求
2
3n×m≤2000n \times m \le 2000n×m2000 min(n,m)≤15\min(n,m) \le 15min(n,m)15
4
5
6
7
8
9无特殊要求
10
11
12
13
14
15
16
17
18
19
20

Source/Category