Flip Game

Interview

Time limit1sMemory limit512 MB

Summary

Given an N x N grid of 0/1 cells, find the fewest operations (flip a whole row or column, or one cell) to make all cells equal.

Level: Medium5 of 10
Topics: Brute force, Bit manipulation, Implementation, Array
Solved: No attempts yet

Problem

Baeknami, an explorer with an E (extraverted) MBTI, is exploring a pyramid said to hide an unknown treasure. After passing fearsome traps, he finds the room with the treasure, but he must solve a riddle to open the treasure chest.

The riddle is as follows.

There are stones painted black on one side and white on the other.
The stones are all placed on an $N \times N$ grid, each showing either black or white.
Find the time needed to make every stone the same color.

Baeknami can take one of the following actions. Each action takes 1 second.

Choose a row or a column of the grid and flip every stone in that line.
Flip a single stone.

Find the minimum time needed to open the treasure chest, and help Baeknami obtain the treasure safely!

Input

The first line gives $N$ , the number of rows and the number of columns of the grid. ( $1\leq N \leq 8$ )

The next $N$ lines give numbers representing the current color of each cell of the grid.

In the $N$ lines, the $j$ -th number of the $i$ -th line represents the color of the cell in row $i$ , column $j$ : ' $0$ ' means black and ' $1$ ' means white.

Output

Find the minimum time needed to make every stone the same color.

Examples2

Example 1
Input
```
2
0 0
0 1
```
Expected output
```
1
```

Example 2

Input

8
0 0 0 0 0 0 1 0
1 1 1 1 1 1 1 1
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 0

Expected output