Amenities Coverage Problem

You are given a grid of size \( M \times N \) representing a set of buildings. Each cell in the grid is either '1' or '0'. A cell with a '1' indicates the presence of an amenity, and an amenity covers all buildings located in any cell whose row and column differences are at most \( D \). In other words, an amenity at cell \( (i,j) \) covers any cell \( (x,y) \) if \( |x-i| \le D \) and \( |y-j| \le D \).

Your task is to determine if every building (each cell in the grid) is within the range of at least one amenity. If every cell is covered by at least one amenity’s range, output True; otherwise, output False.

Note: If there are no amenities at all (i.e. all cells are '0'), then the answer is False.

inputFormat

The input is given from standard input (stdin) and has the following format:

M N D
row1
row2
...
rowM

Where:

• M is the number of rows.
• N is the number of columns.
• D is the range (i.e. maximum allowed difference in both row and column from an amenity cell).
• Each of the next M lines contains N space-separated characters (each either 0 or 1) representing the grid.

outputFormat

Print a single line to standard output (stdout) with either True if every cell in the grid is covered by at least one amenity’s range, or False otherwise.

3 3 1
1 0 1
0 0 0
1 0 1

True