[leetcode] 782. Transform to Chessboard

[leetcode] 782. Transform to Chessboard

Description

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:

2

Explanation:

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:

0

Explanation:

Also note that the board with 0 in the top left corner,0110is also a valid chessboard.

Input:

board = [[1, 0], [1, 0]]

Output:

-1

Explanation:

No matter what sequence of moves you make, you cannot end with a valid chessboard.

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.

分析

题目的意思是：一个n*n的网格里包含0和1，你可以交换任意的行和列，把这个网格变成棋盘，棋盘中的0和1都不是四面相邻的。

这道题比较难，是hard类型的题目。在一个合法的棋盘里面，仅有两种行，这两种行是互逆的，例如有一行是：01010011，其他行一定是01010011或者10101100。列也是一样。一个推论为：矩形棋盘的左上，左下，右上，右下一定是4个1，或者两个1和两个0，或者4个0.另一个重要的属性是每行和每列有一半是1。假设这个棋盘是n*n：如果N=2k,每一行和每一列都包含k个1，如果N=2k+1,每一行和每一列有k个1和k+1个0，或者k+1个1和k个0.

代码

class Solution {public: int movesToChessboard(vector>& board) { int n=board.size(),rowSum=0,colSum=0,rowSwap=0,colSwap=0; for(int i=0;irowSum||rowSum>(n+1)/2) return -1; if(n/2>colSum||colSum>(n+1)/2) return -1; if(n%2){ if (colSwap % 2) colSwap = n - colSwap; if (rowSwap % 2) rowSwap = n - rowSwap; }else{ colSwap=min(n-colSwap,colSwap); rowSwap = min(n - rowSwap, rowSwap); } return (colSwap+rowSwap)/2; }};

参考文献

​​782. Transform to Chessboard​​

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