#281. #2321. 「清华集训 2017」无限之环
-
ID: 281
传统题
1000ms
512MiB
尝试: 0
已通过: 0
难度: (无)
上传者:
#2321. 「清华集训 2017」无限之环
说明
曾经有一款流行的游戏，叫做 Infinity Loop，先来简单的介绍一下这个游戏:
游戏在一个 n×mn \times mn×m 的网格状棋盘上进行，其中有些小方格中会有水管，水管可能在方格某些方向的边界的中点有接口，所有水管的粗细都相同，所以如果两个相邻方格的公共边界的中点都有接头，那么可以看作这两个接头互相连接。水管有以下 151515 种形状：
游戏开始时，棋盘中水管可能存在漏水的地方。
形式化地:如果存在某个接头，没有和其它接头相连接，那么它就是一个漏水的地方。
玩家可以进行一种操作：选定一个含有非直线型水管的方格，将其中的水管绕方格中心顺时针或逆时针旋转 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-1−1.
样例
样例输入 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 的范围 | 特殊约定 |
|---|---|---|
| 1 | n×m≤16n\times m \le 16n×m≤16 | 无特殊要求 |
| 2 | ||
| 3 | n×m≤2000n \times m \le 2000n×m≤2000 | 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 |