{"problem":{"name":"Don't Isolate Elements","description":{"content":"You are given a matrix $A$ with $H$ rows and $W$ columns. The value of each of its elements is $0$ or $1$. For an integer pair $(i, j)$ such that $1 \\leq i \\leq H$ and $1 \\leq j \\leq W$, we denote by ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc283_e"},"statements":[{"statement_type":"Markdown","content":"You are given a matrix $A$ with $H$ rows and $W$ columns. The value of each of its elements is $0$ or $1$. For an integer pair $(i, j)$ such that $1 \\leq i \\leq H$ and $1 \\leq j \\leq W$, we denote by $A_{i,j}$ the element at the $i$\\-th row and $j$\\-th column.\nYou can perform the following operation on the matrix $A$ any number of times (possibly zero):\n\n*   Choose an integer $i$ such that $1 \\leq i \\leq H$. For every integer $j$ such that $1 \\leq j \\leq W$, replace the value of $A_{i,j}$ with $1-A_{i,j}$.\n\n$A_{i,j}$ is said to be **isolated** if and only if there is no adjacent element with the same value; in other words, if and only if none of the four integer pairs $(x,y) = (i-1,j),(i+1,j),(i,j-1),(i,j+1)$ satisfies $1 \\leq x \\leq H, 1 \\leq y \\leq W$, and $A_{i,j} = A_{x,y}$.\nDetermine if you can make the matrix $A$ in such a state that no element is isolated by repeating the operation. If it is possible, find the minimum number of operations required to do so.\n\n## Constraints\n\n*   $2 \\leq H,W \\leq 1000$\n*   $A_{i,j} = 0$ or $A_{i,j} = 1$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$H$ $W$\n$A_{1,1}$ $A_{1,2}$ $\\ldots$ $A_{1,W}$\n$A_{2,1}$ $A_{2,2}$ $\\ldots$ $A_{2,W}$ \n$\\vdots$\n$A_{H,1}$ $A_{H,2}$ $\\ldots$ $A_{H,W}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc283_e","tags":[],"sample_group":[["3 3\n1 1 0\n1 0 1\n1 0 0","1\n\nAn operation with $i = 1$ makes $A = ((0,0,1),(1,0,1),(1,0,0))$, where there is no longer an isolated element."],["4 4\n1 0 0 0\n0 1 1 1\n0 0 1 0\n1 1 0 1","2"],["2 3\n0 1 0\n0 1 1","\\-1"]],"created_at":"2026-03-03 11:01:13"}}