782. Transform to Chessboard

782. Transform to Chessboard

An N x N board contains only 0s and 1s. In each move, you can swap any 2 rows with each other, or any 2 columns with each other.

What is the minimum number of moves to transform the board into a “chessboard” - a board where no 0s and no 1s are 4-directionally adjacent? If the task is impossible, return -1.

Examples:Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]Output: 2Explanation:One potential sequence of moves is shown below, from left to right:0110 1010 10100110 --> 1010 --> 01011001 0101 10101001 0101 0101The first move swaps the first and second column.The second move swaps the second and third row.Input: board = [[0, 1], [1, 0]]Output: 0Explanation:Also note that the board with 0 in the top left corner,0110is also a valid chessboard.Input: board = [[1, 0], [1, 0]]Output: -1Explanation:No matter what sequence of moves you make, you cannot end

Note:

board will have the same number of rows and columns, a number in the range [2, 30]. board[i][j] will be only 0s or 1s.

class Solution public int movesToChessboard(int[][] board) { int N = board.length; // count[code] = v, where code is an integer // that represents the row in binary, and v // is the number of occurrences of that row Map count = new HashMap(); for (int[] row: board) { int code = 0; for (int x: row) code = 2 * code + x; count.put(code, count.getOrDefault(code, 0) + 1); } int k1 = analyzeCount(count, N); if (k1 == -1) return -1; // count[code], as before except with columns count = new HashMap(); for (int c = 0; c < N; ++c) { int code = 0; for (int r = 0; r < N; ++r) code = 2 * code + board[r][c]; count.put(code, count.getOrDefault(code, 0) + 1); } int k2 = analyzeCount(count, N); return k2 >= 0 ? k1 + k2 : -1; } public int analyzeCount(Map count, int N) { // Return -1 if count is invalid // Otherwise, return number of swaps required if (count.size() != 2) return -1; List keys = new ArrayList(count.keySet()); int k1 = keys.get(0), k2 = keys.get(1); // If lines aren't in the right quantity if (!(count.get(k1) == N/2 && count.get(k2) == (N+1)/2) && !(count.get(k2) == N/2 && count.get(k1) == (N+1)/2)) return -1; // If lines aren't opposite if ((k1 ^ k2) != (1< N) // ones start cand = Math.min(cand, Integer.bitCount(k1 ^ 0x55555555 & Nones) / 2); return

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。