Under construction

Still being built. Things may change

Building a Bridge

Interview

Time limit2sMemory limit192 MB

Summary
Given a grid of land and sea, find the shortest straight sea-cell bridge connecting two different islands.
Level

Medium5 of 10

Topics
BFS, Array, Implementation
Solved
No attempts yet

Problem

A country is made of several islands. Its map is given as an N x N grid, where each cell is either sea or land. An island is one connected component of land cells connected vertically or horizontally.

You want to connect two different islands with one bridge. A bridge may be built only on sea cells, and its length is the number of grid cells occupied by the bridge.

Given the map, find the minimum possible length of a bridge that connects two different islands.

Input

The first line contains the map size N. N is a natural number no greater than 100.

Each of the next N lines contains N integers separated by spaces. 0 represents sea, and 1 represents land.

The given map always contains at least two islands.

Output

Print the minimum length of a bridge that connects two different islands.

Examples1

  1. Example 1

    Input
    10
1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
    Expected output
    3