Last updated on October 9th, 2024 at 06:24 pm
Here, We see Transform to Chessboard LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Topics
Hash Table
Level of Question
Hard
Transform to Chessboard LeetCode Solution
Table of Contents
Problem Statement
You are given an n x n binary grid board. In each move, you can swap any two rows with each other, or any two columns with each other.
Return the minimum number of moves to transform the board into a chessboard board. If the task is impossible, return -1.
A chessboard board is a board where no 0‘s and no 1‘s are 4-directionally adjacent.
Example 1:
Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]] Output: 2 Explanation: One potential sequence of moves is shown. The first move swaps the first and second column. The second move swaps the second and third row.
Example 2:
Input: board = [[0,1],[1,0]] Output: 0 Explanation: Also note that the board with 0 in the top left corner, is also a valid chessboard.
Example 3:
Input: board = [[1,0],[1,0]] Output: -1 Explanation: No matter what sequence of moves you make, you cannot end with a valid chessboard.
1. Transform to Chessboard Leetcode Solution C++
class Solution {
public:
int movesToChessboard(vector<vector<int>>& board) {
int n = board.size();
int row_counter = 0, col_counter = 0;
for(int r = 0; r < n; r++){
row_counter += board[r][0] ? 1 : -1;
for(int c = 0; c < n; c++){
if(r == 0) col_counter += board[r][c] ? 1 : -1;
if((board[r][0] ^ board[0][0]) ^ (board[r][c] ^ board[0][c])) return -1;
}
}
if(abs(row_counter) > 1 || abs(col_counter) > 1) return -1;
int row_swap_count = 0, col_swap_count = 0, row_0_count = 0, col_0_count = 0;
for(int i = 0; i < n; i++){
if(i & 1){
row_swap_count += board[i][0];
col_swap_count += board[0][i];
}
row_0_count += board[i][0] == 0, col_0_count += board[0][i] == 0;
}
int odd_position_count = n/2;
if(n & 1){
row_swap_count = row_0_count == odd_position_count ? row_swap_count : (odd_position_count - row_swap_count);
col_swap_count = col_0_count == odd_position_count ? col_swap_count : (odd_position_count - col_swap_count);
}
else{
row_swap_count = min(row_swap_count, odd_position_count - row_swap_count);
col_swap_count = min(col_swap_count, odd_position_count - col_swap_count);
}
return row_swap_count + col_swap_count;
}
};2. Transform to Chessboard Leetcode Solution Java
class Solution {
public int movesToChessboard(int[][] board) {
int N = board.length, rowSum = 0, colSum = 0, rowSwap = 0, colSwap = 0;
for (int r = 0; r < N; ++r)
for (int c = 0; c < N; ++c) {
if ((board[0][0] ^ board[r][0] ^ board[0][c] ^ board[r][c]) == 1)
return -1;
}
for (int i = 0; i < N; ++i) {
rowSum += board[0][i];
colSum += board[i][0];
rowSwap += board[i][0] == i % 2 ? 1 : 0;
colSwap += board[0][i] == i % 2 ? 1 : 0;
}
if (N / 2 > rowSum || rowSum > (N + 1) / 2) return -1;
if (N / 2 > colSum || colSum > (N + 1) / 2) return -1;
if (N % 2 == 1) {
if (colSwap % 2 == 1) colSwap = N - colSwap;
if (rowSwap % 2 == 1) rowSwap = N - rowSwap;
} else {
colSwap = Math.min(N - colSwap, colSwap);
rowSwap = Math.min(N - rowSwap, rowSwap);
}
return (colSwap + rowSwap) / 2;
}
}3. Transform to Chessboard Leetcode Solution JavaScript
var movesToChessboard = function (board) {
let boardSize = board.length;
let boardSizeIsEven = boardSize % 2 === 0;
if (!canBeTransformed(board)) return -1;
let rowSwap = 0;
let colSwap = 0;
let rowSwap2 = 0;
let colSwap2 = 0;
for (let i = 0; i < boardSize; i++) {
if (board[i][0] === i % 2) {
rowSwap++;
} else {
rowSwap2++;
}
if (board[0][i] === i % 2) {
colSwap++;
} else {
colSwap2++;
}
}
if ((rowSwap + colSwap) === 0 || (rowSwap2 + colSwap2) === 0) return 0;
if (boardSizeIsEven) {
rowSwap = Math.min(rowSwap, rowSwap2);
colSwap = Math.min(colSwap, colSwap2);
} else {
rowSwap = rowSwap % 2 === 0 ? rowSwap : rowSwap2;
colSwap = colSwap % 2 === 0 ? colSwap : colSwap2;
}
return (rowSwap + colSwap) / 2;
function canBeTransformed(board) {
let sum = board[0].reduce((a, b) => a + b);
if (boardSizeIsEven && sum != boardSize / 2) return false;
if (!boardSizeIsEven && sum > ((boardSize + 1) / 2)) return false;
let first = board[0].join('');
let opposite = board[0].map((item) => item === 1 ? 0 : 1).join('');
let counter = [0, 0];
for (let i = 0; i < boardSize; i++) {
let str = board[i].join('');
if (str == first) {
counter[0]++;
} else if (str == opposite) {
counter[1]++;
} else {
return false;
}
}
if (boardSizeIsEven) {
return counter[0] == counter[1];
}
return Math.abs(counter[0] - counter[1]) === 1
}
}; 4. Transform to Chessboard Solution Python
class Solution(object):
def movesToChessboard(self, board):
self.set_up_for_processing_board(len(board))
return self.process_board(board)
def check_even(self, count) :
if len(count) != 2 or sorted(count.values()) != self.balanced :
return -1
return 1
def all_opposite(self, line1, line2) :
if not all (line1_value ^ line2_value for line1_value, line2_value in zip(line1, line2)) :
return -1
return 1
def set_sums_of_lists_of_values(self) :
self.sums_of_lists_of_values = [sum(list_of_values) for list_of_values in self.lists_of_values]
def update_number_of_swaps(self) :
self.number_of_swaps += min(self.sums_of_lists_of_values) // 2
def set_lists_of_values(self, line1) :
self.lists_of_values = []
for start in self.starts :
new_list = []
for index, value in enumerate(line1, start) :
new_list.append((index-value) % 2)
self.lists_of_values.append(new_list)
def set_starting_values(self, line1) :
self.starts = [+(line1.count(1) * 2 > self.n)] if self.n & 1 else [0, 1]
def process_line(self, line1) :
self.set_starting_values(line1)
self.set_lists_of_values(line1)
self.set_sums_of_lists_of_values()
self.update_number_of_swaps()
def process_board(self, board) :
for count in (collections.Counter(map(tuple, board)), collections.Counter(zip(*board))) :
if self.check_even(count) == -1 :
return -1
line1, line2 = count
if self.all_opposite(line1, line2) == -1 :
return -1
self.process_line(line1)
return self.number_of_swaps
def set_up_for_processing_board(self, n) :
self.n = n
self.number_of_swaps = 0
self.balanced = [n//2, (n+1)//2]