Checkerboard by Swapping Lines

Hard

You are given a square n × n grid grid of zeros and ones. In one move you may swap any two rows or any two columns. A grid is a **checkerboard** when no two cells that share a side hold the same value. The top-left corner may be either 0 or 1. Return the minimum number of moves needed to turn the grid into a checkerboard, or -1 if it cannot be done.

Example 1

grid=[[1, 1, 0, 0], [0, 0, 1, 1], [0, 0, 1, 1], [1, 1, 0, 0]] → 2

Swapping columns 1 and 2 makes every row alternate. Then swapping rows 2 and 3 (or 0 and 1) makes the columns alternate too. That is 2 swaps, and it cannot be done faster.

Example 2

grid=[[1, 0, 1], [0, 1, 0], [1, 0, 1]] → 0

The grid is already a checkerboard, so nothing needs to move.

Example 3

grid=[[1, 1], [0, 0]] → -1

Both cells in each row are equal, and no reordering of rows or columns can change that.

Constraints

2 ≤ n ≤ 30
len(grid) = len(grid[i]) = n
grid[i][j] is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Array Math Matrix

Similar problems

Switch Lines to Darken the Board Medium Where the Friends Should Meet Hard Two Groups With the Same Average Hard XOR Tile Duel Hard Keys and Doors in a Maze Hard

Input

grid=[[1, 1, 0, 0], [0, 0, 1, 1], [0, 0, 1, 1], [1, 1, 0, 0]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 78 tests on the server, hidden ones included.