## 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