AIOC Banner

Problem: Invasion

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


Input File: invin.txt
Output File: invout.txt
Time Limit: 1 second

As a highly-trained and razor-sharp military strategist, you have decided that it is time to establish your own empire. Unfortunately you do not have an army with which to do this: since the hushed-up incident with the pet hamster and the nuclear power plant, you were exiled from your former nation and nowadays you are on your own.

Your grand plan requires you to find a new nation to join forces with. You will then immediately invade all of its neighbours, taking them completely by surprise. Of course your empire will probably end there, since your forces will be so stretched at this point that you will not be able to expand any further.

The first decision for you to make is which nation to join forces with. You have acquired a map that shows the boundaries of the nations in your region. You wish to invade as many countries as possible, which means you must choose a nation with as many neighbours as possible.

Military maps are of course highly structured, and this map is no exception. It consists of a large grid of square cells, where each nation is formed from some group of cells. An example map on a 3  x  6 grid of cells is shown below, describing the nine nations a, b, ..., i.


Two nations are considered neighbours if they own land that is vertically or horizontally adjacent (for instance, a and d are neighbours in the example above, but a and e are not since they only touch at a corner).

Your task is to find the largest number of countries that you can invade, that is, the largest number of neighbours that any single nation has.


The input will contain a map of the region. Each nation will be denoted by a lower-case letter of the alphabet. There will be at most twenty-six nations on the map, and each cell of the map will belong to some nation.

The first line of input will contain two integers r and c separated by a single space, where r and c are the number of rows and columns respectively in the map ( 1  <= r  <= 1000 and 1  <= c  <= 1000).

Following this will be the map itself, formed from r lines each containing c lowercase letters describing which nation owns each cell. It is guaranteed that each nation will form a single connected region (that is, you can walk from any part of a nation to any other part of that same nation without walking on land owned by anyone else).


Your output file must consist of a single integer, giving the largest number of neighbours that a single nation has.

Sample Input

3 6

Sample Output



The sample input shows the map illustrated earlier. Here nation g has borders with nations c, f, h and i, giving it a total of four neighbours. The other nations only have two or three neighbours each (b, c, e and f each have three, and a, d, h and i each have two). Therefore the largest number of neighbours that a single nation has is four.


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


Privacy statement
© Australian Mathematics Trust 2001-2023

Page generated: 24 March 2023,  8:00pm AEDT