Problem

Submissions

Solution

New

Discuss

0

Difficulty: MEDIUM

Avg. time to solve

35 min

Success Rate

65%

Problem Statement

Suggest Edit

```
The distance is calculated as |i1 – i2| + |j1 – j2|, where i1, j1 are the coordinates of the current cell and i2, j2 are the coordinates of the nearest cell having value 1.
```

```
You can only move in four directions which are : Up, Down, Left and Right.
```

```
If N = 3, M = 4
and mat[ ][ ] = { 0, 0, 0, 1,
0, 0, 1, 1,
0, 1, 1, 0 }
then the output matrix will be
3 2 1 0
2 1 0 0
1 0 0 1
```

```
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases are as follows.
The first line of each test case contains two space-separated integers ‘N’ and ‘M’ which denotes the size of the matrix.
The ‘N’ lines of each test case contain ‘M’ space-separated elements of the matrix.
```

```
For each test case, print a matrix of the same size containing the distance of the nearest cell having ‘1’ for each cell.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 5
1 <= N <= 2*10^2
1 <= M <= 2*10^2
Where ‘T’ is the number of test cases, ‘N’ is the number of rows in the matrix and ‘M’ is the number of columns in the matrix.
```

```
1
3 4
0 0 0 1
0 0 1 1
0 1 1 0
```

```
3 2 1 0
2 1 0 0
1 0 0 1
```

```
1
3 3
1 0 0
0 0 1
0 1 1
```

```
0 1 1
1 1 0
1 0 0
```

Console