Zoning

Interview

Time limit2sMemory limit512 MB

Summary

Given an n by n grid labeled 1, 2, 3, find the maximum over all cells labeled 1 of the Manhattan distance to the nearest cell labeled 3.

Level: Medium6 of 10
Topics: BFS, Graph, Matrix, Shortest path
Solved: No attempts yet

Problem

A town is usually divided into zones such as industrial zones, commercial zones, and residential zones. If a residential zone sits far away from every commercial zone, the people who live there face a long trip whenever they want to go shopping, and that is undesirable.

The town is given as an $n \times n$ grid of square zones. Each zone is labeled 1 for residential, 2 for industrial, or 3 for commercial. When you travel from one zone to another you may move north, east, south, or west, and the distance travelled is the number of zone boundaries you cross. So the distance between two adjacent zones is 1, and the distance from the zone in square $(1, 1)$ , the most south westerly zone, to the zone in square $(2, 3)$ is 3: one step east and two steps north. You may never move off the grid.

For every residential zone, measure the distance to the commercial zone closest to it. Report the largest of those distances.

Input

The first line contains an integer $n$ ( $2 \le n \le 1500$ ). Each of the next $n$ lines contains a string of length $n$ , giving the map of the town as an $n \times n$ matrix where every entry is 1, 2, or 3 according to the zone type. The town contains at least one zone of each of the three types.

Output

Print a single integer $d$ , the largest distance from a residential zone to its closest commercial zone.

Examples2

Example 1
Input
```
4
1223
2123
2213
3212
```
Expected output
```
3
```
Example 2
Input
```
2
12
33
```
Expected output
```
1
```