Taeyoung Throws Bombs
InterviewTime limit2sMemory limit512 MB
Given the altitude grid after all first explosions, recover how many bombs landed at each cell, where each bomb lowers an MxM square by 1.
- Level
Medium6 of 10
- Topics
- Prefix sum, Implementation, Array, Simulation
- Solved
- No attempts yet
Problem
Taeyoung, having failed his exam, throws bombs at Inha University!
Inha University is a square plot of land of size N×N. All of the land is divided into 1×1 square cells. Each cell is denoted by (r, c), where r is the number of cells from the top and c is the number of cells from the left. r and c start at 0.
Initially, every cell of Inha University has an altitude of 0 meters. However, when Taeyoung throws a bomb, the altitude of every cell within the blast range decreases by 1 meter, and the bomb remains where it landed. The blast range of a bomb Taeyoung throws is a square region of size M×M centered on the cell where the bomb landed. M is odd, and the top edge of the blast range is parallel to the top edge of Inha University. Taeyoung never throws a bomb so that its blast range goes beyond Inha University.
The bombs Taeyoung throws are designed to explode not just once but once more 3 days later. You are given the altitude of Inha University after Taeyoung threw the bombs and all of them finished their first explosion. The altitude of each cell is H[r][c]. Our task is to find, for every cell, how many bombs are there, before the bombs explode once more 3 days later.
Input
The positive integers N and M are given, separated by a space.
N lines follow, giving the values of the array H. The c-th value on the r-th line is H[r][c].
Output
Output N lines, each containing N integers.
The c-th value on the r-th line is the number of bombs at (r, c).
Constraints
- 1 ≤ M ≤ N ≤ 2,000 (M is odd)
- -2,147,483,648 ≤ H[r][c] ≤ 0