{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e .sampledata { font-family: \"Courier New\", Courier, monospace; white-space: pre; }\u003c/style\u003e\u003cdiv\u003e \n \u003cdiv\u003e\n 曾经有一款流行的游戏,叫做InfinityLoop,先来简单的介绍一下这个游戏:\n \u003c/div\u003e \n \u003cdiv\u003e\n 游戏在一个n×m的网格状棋盘上进行,其中有些小方格中会有水管,水管可能在方格某些方向的边界的中点有接口\n \u003c/div\u003e \n \u003cdiv\u003e\n ,所有水管的粗细都相同,所以如果两个相邻方格的公共边界的中点都有接头,那么可以看作这两个接头互相连接\n \u003c/div\u003e \n \u003cdiv\u003e\n 。水管有以下15种形状:\n \u003c/div\u003e \n \u003cdiv\u003e\n \u003cimg SRC\u003d\"CDN_BASE_URL/687c21cb6627dd0f90f4a824a37f5f41?v\u003d1591079909\" width\u003d\"430\" height\u003d\"228\" alt\u003d\"\"\u003e\n \u003c/div\u003e \n \u003cdiv\u003e\n 游戏开始时,棋盘中水管可能存在漏水的地方。\n \u003c/div\u003e \n \u003cdiv\u003e\n 形式化地:如果存在某个接头,没有和其它接头相连接,那么它就是一个漏水的地方。\n \u003c/div\u003e \n \u003cdiv\u003e\n 玩家可以进行一种操作:选定一个含有非直线型水管的方格,将其中的水管绕方格中心顺时针或逆时针旋转90度。\n \u003c/div\u003e \n \u003cdiv\u003e\n 直线型水管是指左图里中间一行的两种水管。\n \u003c/div\u003e \n \u003cdiv\u003e\n 现给出一个初始局面,请问最少进行多少次操作可以使棋盘上不存在漏水的地方。\n \u003c/div\u003e \n\u003c/div\u003e \n\u003cp\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv\u003e\n 第一行两个正整数n,m代表网格的大小。\n\u003c/div\u003e \n\u003cdiv\u003e\n 接下来n行每行m数,每个数是[0,15]中的一个\n\u003c/div\u003e \n\u003cdiv\u003e\n 你可以将其看作一个4位的二进制数,从低到高每一位分别代表初始局面中这个格子上、右、下、左方向上是否有水管接头。\n\u003c/div\u003e \n\u003cdiv\u003e\n 特别地,如果这个数是000,则意味着这个位置没有水管。\n\u003c/div\u003e \n\u003cdiv\u003e\n 比如3(0011(2))代表上和右有接头,也就是一个L型,而12(1100(2))代表下和左有接头,也就是将L型旋转180度。\n\u003c/div\u003e \n\u003cdiv\u003e\n n×m≤2000\n\u003c/div\u003e \n\u003cp\u003e\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv\u003e\n 输出共一行,表示最少操作次数。如果无法达成目标,输出-1\n\u003c/div\u003e \n\u003cp\u003e\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e2 3\r\n3 14 12\r\n3 11 12\u003c/span\u003e\u003c/div\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e2\u003c/span\u003e\u003c/div\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\u0026nbsp;样例1棋盘如下\u003c/p\u003e\n\u003cbr\u003e \n\u003cdiv\u003e\n 旋转方法很显然,先将左上角虚线方格内的水管顺时针转90度\n\u003c/div\u003e\n\u003cbr\u003e \n\u003cdiv\u003e\n \u003cimg SRC\u003d\"CDN_BASE_URL/cfad0606132874852aaa3911bbf9bf05?v\u003d1591079909\" width\u003d\"192\" height\u003d\"270\" alt\u003d\"\"\u003e\n\u003c/div\u003e\n\u003cbr\u003e \n\u003cdiv\u003e\n 然后右下角虚线方格内的水管逆时针旋转90度,这样就使得水管封闭了\n\u003c/div\u003e\n\u003cp\u003e\u003c/p\u003e"}}]}