All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Mosaics and holes

Algorithms, Greedy algorithm, Greedy algorithm, Greedy algorithm


John wants to cover his yard floor with mosaics. The yard floor is a \(n \times m\) matrix and each cell is either a mosaic or a hole. John has invented a flipper machine. This machine has a size of \(k\) and can select a \(k \times k\) square of the yard and flip the cells in it. By this action, every hole in the square becomes a mosaic and every mosaic in the square becomes a hole. It is illustrated by the following example:

The \(2 \times 2\) square on the left has been flipped to the right one by the flipper with the size \(2\) and blacks are holes and whites are mosaics.

Help John to cover the floor of the yard completely by mosaics by using this machine. In each step, John selects a \(k \times k \) square of the yard floor and sets the machine on it. He wants to compute the minimum steps needed to repair the yard floor.

Input Format

  • First line: Three integers \(n, m, k\) (\(1 \leq n, m \leq 1000 , 1 \leq k \leq min(n,m)\)), where \(n\) is the number of matrix rows, \(m \) as the number of matrix columns, and \(k\) as the size of the flipper machine.
  • Next n lines: Each line will contain m integer 0 or 1 with space in between the consecutive one.
  • This \(n\) lines are the data of the yard floor matrix, 1 indicates that the cell is mosaic and 0 indicates that the cell is a hole.

Output format

Print an integer denoting the minimum number of steps needed to repair the yard floor or -1 if it is impossible to repair the yard floor with this machine.

2 3 2
0 1 0
0 1 0

we can repair the yard by 2 steps as shown below.

you can see more sample tests here!

Sample Input Sample output

3 3 2

0 0 0

0 1 0

0 0 0





2 2 1

0 0

0 0





Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications