AIOC Banner

Problem: Escape from Civilisation

Want to try solving this problem? You can submit your code online if you log in or register.


Escape from Civilisation

Time Limit: 1 second
Memory Limit: 30 Mb

After too many years as a computer programmer, you decide it's time to retire and get in touch with your inner child. You hurriedly pack up all of your non-technological belongings (which isn't all that much) and head away from the city, away from the Internet, away from civilisation, and into the country, to live a simple life.

However, before you can be on your way, you need to write one last program. You wish to be as far away from civilisation as possible — in one of the most isolated areas known to humanity. You possess a map of width w and height h. This map tells you where the areas of civilisation can be found. The most isolated areas are those map squares that have the furthest Manhattan distance from any civilisation. The Manhattan distance between two squares is the sum of the up/down distance and the left/right distance, as illustrated below.

Your task is to determine how far the most isolated areas are from civilisation.

Constraints

Furthermore, for 30% of the available marks, the dimensions of the map will satisfy w,h <= 50.

Example

Consider the map below, of width 10 and height 11. Areas of civilisation are shaded. The two squares marked with an  x  are the most isolated squares — no other map squares are further from civilisation than these. The marked squares each have Manhattan distance 3 from the nearest civilisation, and so the answer to the problem is 3.

Input

Your program must read from standard input. The first line will contain two positive integers w and h, separated by a single space. The following h lines will each contain w integers. Each of these integers will either be a 1, denoting the presence of civilisation, or a 0, denoting no civilisation.

Output

Your program must write a single line to standard output. This line must contain a single integer, giving the Manhattan distance from civilisation to the most isolated map square.

Sample Input

10 11
1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 0 1 0 0 1
1 0 0 0 0 0 0 1 1 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 0 0 0
1 1 0 0 0 1 1 1 0 0
1 1 0 0 1 1 1 0 0 1
1 0 1 1 1 1 0 0 0 1
1 0 0 1 1 0 0 0 0 1
0 0 1 1 0 0 0 0 0 1
0 0 1 1 1 1 1 1 1 1

Sample Output

3

Scoring

The score for each input scenario will be 100% if the correct answer is output, or 0% otherwise.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 15 November 2019,  5:33am AEDT