Solved-A13- Solution

Description

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

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

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:

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