426. Minimum Swaps for Chessboard Transformation
0
Hard
M.S. Dhoni and Virat Kohli have a strong interest in chess. Virat presents Dhoni with a square matrix of size N × N, filled with only zeros and ones. Dhoni's task is to transform the given matrix into a chessboard configuration. To achieve this, Dhoni can perform the following operations:
NOTE: In a chessboard, no adjacent elements (vertically or horizontally) are the same. Therefore, the chessboard may start with a 0 in the top-left corner.
- Swap any two rows of the matrix.
- Swap any two columns of the matrix.
NOTE: In a chessboard, no adjacent elements (vertically or horizontally) are the same. Therefore, the chessboard may start with a 0 in the top-left corner.
Input Format
The first line contains an integer N, representing the size of the matrix. The next N lines contain N space-separated 0's or 1's, representing the elements of the matrix.
Output Format
Print the minimum number of swaps required.
If it is impossible to obtain a chessboard configuration from the given matrix, print -1.
If it is impossible to obtain a chessboard configuration from the given matrix, print -1.
Example
Input
4
0 1 1 0
0 1 1 0
1 0 0 1
1 0 0 1
Output
2
Constraints
2 <= N <= 30
Aij = 0 or 1
Aij = 0 or 1
Loading...
View Submissions
Console