Card Flipping

Time limit5sMemory limit128 MB

Summary
Given an R by 16 grid of target flip states, find the minimum number of contiguous row or column flip operations to turn all cards from face up to the required pattern.
Level

Hard8 of 10

Topics
Dynamic programming, Bit manipulation, Matrix, Greedy
Solved
No attempts yet

Problem

There is an array of cards with R rows and 16 columns. Every card initially shows its front side. Each cell is marked with either 0 or 1. Cards marked 0 must end face up, and cards marked 1 must end face down.

In one operation, you may choose a contiguous group of cards in one row, or a contiguous group of cards in one column, and flip all chosen cards. A flipped card changes between front and back.

Find the minimum number of operations needed to reach the target state. Minimize the number of operations, not the total number of flipped cards.

Input

The first line contains the number of rows R (1 <= R <= 50). Each of the next R lines contains a string of length 16. Every character is either 0 or 1. A 0 means the card must end face up, and a 1 means the card must end face down.

Output

Print the minimum number of flip operations needed to reach the target state.

Examples2

  1. Example 1

    Input
    5
0000111111110000
0010000000000000
1101111111111111
0010000000000000
0000000000000000
    Expected output
    3

  2. Example 2

    Input
    4
0000001000000010
0000110111000011
0111001000001111
0000001000000011
    Expected output
    6