Problem Statement 6: Corleone’s gangwars
"When you want something, all the universe conspires in helping you achieve it."
Langdon got help from Santiago in completing his mission of cracking the code to the secure vault. Thereafter, he had to meet up with Sophie Neveu in NYC and left Santiago at Long Island. It was here that Santiago heard of the story of Don Vito Corleone – the resplendent mafia who had landed on Long Island with nothing but dreams. Santiago, being a big dreamer himself, couldn’t wait to meet the man.
When he finally got a chance, Vito Corleone’s fortunes were sagging as a rival mafia was on the ascendancy. Looking for all the help he could muster, Vito Corleone asked Santiago to help him out in strategising a gang war. Vito needs to figure out the minimum distance that each of his men need to travel in order to get to a nearest friendly area.
Given a map, in the form of a square matrix containing 0’s and 1’s (0’s representing Corleone’s enemy grids and 1’s Corleone’s friendly grids), the task is to figure out the distance of the closest Corleone’s friendly grid for each grid. The distance between grids (i,j) and (x,y) is defined by
(i-x)*(i-x) + (j-y)*(j-y)
Input: The first line contains the number of test cases.
For each test case, the first line specifies the dimension of the square grid, N. This is followed by n lines, each containing n integers (0’s or 1’s), separated by white spaces.
N <= 1000
Output: For each test case, generate an nxn matrix printed over n rows and each row containing n integers. The (i,j) entry of this output matrix is the minimum distance of a friendly grid from that point.