All submissions for this problem are available.
Leonardo Da Vinci was recently appointed the mayor of the town Vinci. During his first
day, he saw that a lot of (electrical) energy is being wasted in the town. In order to
bring down the energy consumption, he wanted to change the way the street lights worked.
The town of Vinci has N * M street lights arranged in an N by M
grid. To save energy, Leonardo decided that no two adjacent street lights should be ON. Also, no two
adjacent street lights can be OFF because that area would become dark.
You are given the state of all street lights on the grid. You can do one type of operation:
toggle the state of any street light. What are the minimum number of operations needed such
that no two adjacent street lights are ON and no two adjacent street lights are OFF.
Two street lights are adjacent if they are in the same row or the same column and they are placed at consecutive positions in that row or column.
The first line of input contains 2 space-seperated integers N and M.
Next, N lines follow,
each containing a string of length M. Each character in the string is either '0' or '1'.
The jth character in the ith line denotes the state of the street light at position (i, j). '0' denotes ON and '1' denotes OFF.
Print one integer, the answer to the problem.
- 1 ≤ N ≤ 500
- 1 ≤ M ≤ 500
2 3 110 101
We can toggle the state of the street light at (0,0) and the resulting grid
satisfies all the required conditions.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
Fetching successful submissions