Coin Flips II
Time limit2sMemory limit128 MB
Given an N by M grid of coins, find the minimum number of top-left rectangle flips needed to turn every coin to heads.
- Level
Medium6 of 10
- Topics
- Matrix, Greedy, Bit manipulation
- Solved
- No attempts yet
Problem
Sejun has N×M coins arranged in a rectangle with N rows and M columns. A coin showing heads is written as 0, and a coin showing tails is written as 1.
In one move, Sejun chooses a cell (a, b). Then every coin in a cell (i, j) satisfying 1 ≤ i ≤ a and 1 ≤ j ≤ b is flipped at the same time. Here, i is the row number counted from the top, and j is the column number counted from the left.
Find the minimum number of moves needed to make every coin show heads. Even if choosing (a, b) flips a×b coins, it counts as one move, not a×b moves.
Input
The first line contains the height N and width M. N and M are positive integers no greater than 100.
The next N lines each contain M characters describing the coin states. Each character is either 0 or 1.
Output
Print the minimum number of moves needed to make every coin show heads.