Starting from:
$30

$24

A13 Solution

Hackerrank Link: https://www.hackerrank.com/assignment-13




Problem Statement



As you know Covid-19 cases are increasing dramatically so it is necessary for rapid testing and treatment.Doctors and Nurses are working day and night to test and treat Covid-19 patients.




So given a city X in India which has some government registered hospitals for Covid-19 treatment,your task is to nd the nearest such hospital so people living in a particular location can avail test and treatment as soon as possible once they show symptoms of Covid-19.The city X is given in the form of a matrix N x M,where H represents the Covid-19 hospitals and other locations are given as Ls. So for each such location given in the form of L(x1; y1),you have to nd the distance of the nearest hospital .The distance is calculated as ji1{i2j + jj1{j2j, where i1, j1 are the row number and column number of the current cell and i2, j2 are the row number and column number of the nearest cell having value H,i.e. the Covid-19 hospital.(Note:While calculating the distances,it should be either row-wise or column-wise and not diagonally.)




You have to give an e cient implementation for the given problem.




Input Format



N M //N and M denotes the number of rows and columns of the input matrix.




Inputs of the matrix elements in the terms of L and H.




Output Format



An output matrix containing the minimum distances to the nearest Hospital(H)




from each cell.













1












Constraints



1<=N<=500




1<=M<=500




Its given that there will be atleast 1 Hospital in a given N*M matrix.




Sample Testcase



Input:




4 4




HLLL




LLLH




LLHL




HLLH




Output:




0121




1210




1101




0110




Explanation:




For location(L) at (0,1), nearest H is at (0,0),




So distance = j(0 0) + (1 0)j = 1




For a location(L) at (1,1) having nearest Hospital H at (0,0) diagonally, distance = j(1 0) + (1 0)j = 2

Similarly all the distances can be calculated.









































































2

More products