Under construction

Still being built. Things may change

Easy Shortest Distance

Time limit1sMemory limit128 MB

Summary
Given a grid with one target cell and blocked cells, find the shortest distance from each open cell to the target using 4-directional moves.
Level

Easy3 of 10

Topics
BFS, Graph, Matrix
Solved
No attempts yet

Problem

You are given a map. For every cell, find the shortest distance to the target cell.

To keep the problem easy, you may move only up, down, left, and right. One move to an adjacent cell adds 1 to the distance, and blocked land cannot be entered.

Input

The first line contains the map size nn and mm, where nn is the height and mm is the width. (2≤n≤10002 \le n \le 1000, 2≤m≤10002 \le m \le 1000)

Each of the next nn lines contains mm numbers separated by spaces. 0 is blocked land, 1 is open land, and 2 is the target cell. Exactly one 2 appears in the whole input.

Output

Print nn lines with mm numbers each, separated by spaces. The cc-th number on the rr-th line is the shortest distance from the cell in row rr, column cc to the target cell.

Print 0 for a cell of blocked land. Print -1 for a cell of open land that cannot reach the target cell. The target cell itself prints 0.

Examples2

  1. Example 1

    Input
    15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
    Expected output
    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
11 12 13 14 15 16 17 18 19 20 0 0 0 0 25
12 13 14 15 16 17 18 19 20 21 0 29 28 27 26
13 14 15 16 17 18 19 20 21 22 0 30 0 0 0
14 15 16 17 18 19 20 21 22 23 0 31 32 33 34

  2. Example 2

    Input
    4 6
2 1 1 1 1 1
1 1 0 0 0 1
1 1 0 1 0 1
1 1 0 0 0 1
    Expected output
    0 1 2 3 4 5
1 2 0 0 0 6
2 3 0 -1 0 7
3 4 0 0 0 8