diff options
-rw-r--r-- | transform_to_chessboard.c | 57 | ||||
-rw-r--r-- | transform_to_chessboard.py | 50 |
2 files changed, 107 insertions, 0 deletions
diff --git a/transform_to_chessboard.c b/transform_to_chessboard.c new file mode 100644 index 0000000..efe2031 --- /dev/null +++ b/transform_to_chessboard.c @@ -0,0 +1,57 @@ +// 782. Transform to Chessboard +#include "leetcode.h" + +/* + * you are given an 'n * 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 rwos to transform the board intoa 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 + */ + +int movesToChessboard(int **board, int boardSize, int *boardColSize) { + int n = boardSize, row_sum = 0, col_sum = 0, row_swap = 0, col_swap = 0; + for (int i = 0; i < n; ++i) + for (int j = 0; j < n; ++j) + if (board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j]) + return -1; + for (int i = 0; i < n; ++i) { + row_sum += board[0][i]; + col_sum += board[i][0]; + row_swap += board[i][0] == i % 2; + col_swap += board[0][i] == i % 2; + } + if (row_sum != n / 2 && row_sum != (n + 1) / 2) + return -1; + if (col_sum != n / 2 && col_sum != (n + 1) / 2) + return -1; + if (n % 2) { + if (col_swap % 2) + col_swap = n - col_swap; + if (row_swap % 2) + row_swap = n - row_swap; + } else { + col_swap = fmin(n - col_swap, col_swap); + row_swap = fmin(n - row_swap, row_swap); + } + return (col_swap + row_swap) / 2; +} + +int main() { + int b1i[4][4] = {{0, 1, 1, 0}, {0, 1, 1, 0}, {1, 0, 0, 1}, {1, 0, 0, 1}}; + int b2i[2][2] = {{0, 1}, {1, 0}}; + int b3i[2][2] = {{1, 0}, {1, 0}}; + struct two_d_arr b1, b2, b3; + two_d_arr_init(&b1, 4, 4, b1i); + two_d_arr_init(&b2, 2, 2, b2i); + two_d_arr_init(&b3, 2, 2, b3i); + printf("%d\n", + movesToChessboard(b1.arr, b2.row_size, b3.col_size)); // expect: 2 + printf("%d\n", + movesToChessboard(b2.arr, b2.row_size, b2.col_size)); // expect: 0 + printf("%d\n", + movesToChessboard(b3.arr, b3.row_size, b3.col_size)); // expect: -1 + two_d_arr_free(&b1); + two_d_arr_free(&b2); + two_d_arr_free(&b3); +} diff --git a/transform_to_chessboard.py b/transform_to_chessboard.py new file mode 100644 index 0000000..e78edff --- /dev/null +++ b/transform_to_chessboard.py @@ -0,0 +1,50 @@ +# 782. Transform to Chessboard + +""" +you are given an 'n 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 rwos to transform the board intoa 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 +""" + + +class Solution(object): + def movesToChessboard(self, board): + """ + :type board: List[List[int]] + :rtype: int + """ + n = len(board) + if any( + board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j] + for i in range(n) + for j in range(n) + ): + return -1 + if not n / 2 <= sum(board[0]) <= (n + 1) / 2: + return -1 + if not n / 2 <= sum(board[i][0] for i in range(n)) <= (n + 1) / 2: + return -1 + col = sum(board[0][i] == i % 2 for i in range(n)) + row = sum(board[i][0] == i % 2 for i in range(n)) + if n % 2: + if col % 2: + col = n - col + if row % 2: + row = n - row + else: + col = min(n - col, col) + row = min(n - row, row) + return (col + row) / 2 + + +if __name__ == "__main__": + obj = Solution() + print( + obj.movesToChessboard( + board=[[0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1], [1, 0, 0, 1]] + ) + ) + print(obj.movesToChessboard(board=[[0, 1], [1, 0]])) + print(obj.movesToChessboard(board=[[1, 0], [1, 0]])) |