Description
1 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 find 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 find the
distance of the nearest hospital .The distance is calculated as |i1–i2| + |j1–j2|,
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 efficient implementation for the given problem.
2 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.
3 Output Format
An output matrix containing the minimum distances to the nearest Hospital(H)
from each cell.
1
4 Constraints
1 <= N <= 500
1 <= M <= 500
Its given that there will be atleast 1 Hospital in a given N*M matrix.
5 Sample Testcase
Input:
4 4
HLLL
LLLH
LLHL
HLLH
Output:
0 1 2 1
1 2 1 0
1 1 0 1
0 1 1 0
Explanation:
For location(L) at (0,1), nearest H is at (0,0),
So distance = |(0 − 0) + (1 − 0)| = 1
For a location(L) at (1,1) having nearest Hospital H at (0,0) diagonally,
distance = |(1 − 0) + (1 − 0)| = 2
Similarly all the distances can be calculated.
2
