ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2013

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Game Optimization

Time limit: 2.0 second
Memory limit: 64 MB
‘Is anything not working again?’
‘It works, but too slowly. I must constantly recalculate the distance from the ship to the nearest base to check if we can teleport the ship there. When there are too many bases on the map, it works very slowly.’
‘Is the map discrete?’
‘Yes. The map is an n× m grid made up of square cells. Ships and bases can be located at the centers of the cells only.’
‘Then you can precalculate the distances to the nearest base from the centers of each cell.’
‘That’s true. Let’s try it.’


The first line contains integers n and m (1 ≤ n, m ≤ 1 000), which are the numbers of rows and columns in the grid that makes up the map. Then you are given an n× m matrix consisting of zeros and ones. One means that there is a base at the center of the corresponding cell, and zero means that there is no base at that cell. It is guaranteed that there is at least one base and at least one free cell on the map.


Output n lines with m integers in each line. The j-th number in the i-th line must be equal to the squared distance from the center of the cell (i, j) to the nearest base (1 ≤ in; 1 ≤ jm). The numbers in each line must be separated by a space.


3 4
0 1 4 5 
1 2 1 2 
4 1 0 1 
Problem Author: Idea by Ilya Bushkov
Problem Source: Ural Sport Programming Championship 2013
To submit the solution for this problem go to the Problem set: 1976. Game Optimization