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

**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.

- 1 <=
*w*,*h*<= 1,000, where*w*is the width of the map, and*h*is the height of the map; - you are guaranteed there will always be at least one map square of civilisation and one map square with no civilisation.

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.

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.

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.

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

3

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

Privacy
statement

© Australian Mathematics Trust 2001-2021

Page generated: 1 December 2021, 11:22am AEDT