819. Swaps To ChessBoard
0
Hard
M.S. Dhoni and Virat Kohli have a strong interest in chess. Virat presents Dhoni with an N x N array filled with only zeroes and ones. Dhoni's task is to transform the given array into a chessboard. To achieve this, Dhoni can perform the following operations:
NOTE: In a ChessBoard, no adjacent elements (vertically or horizontally) are the same. Therefore, the board may start with a 0 in the top-left corner.
- Swap any two rows
- Swap any two columns
NOTE: In a ChessBoard, no adjacent elements (vertically or horizontally) are the same. Therefore, the board may start with a 0 in the top-left corner.
Input Format
The first line contains an integer N.
The next N lines contain N space-separated 0's or 1's, representing the matrix.
Output Format
Print the minimum number of swaps required.
If it is impossible to obtain a chessboard from the matrix, print -1.
If it is impossible to obtain a chessboard from the 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