Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem S. 105. (February 2016)

S. 105. You are given an \(\displaystyle N\times M\) map (\(\displaystyle 1\le N, M\le 50\)) containing at most 15 islands. The land, deep water and shallow water are denoted by `X', `.' and `S', respectively. Every island is a connected set of X characters.

Bob can swim along any of the four directions parallel to the four sides of the rectangular map. He lands on a chosen island with parachute, and his goal is to visit all islands. He can walk well on land, but he cannot swim in deep water. He can swim in shallow water but he wants to avoid this as much as possible: he wants to minimize the number of S fields he steps on during his journey.

Your program should read the values of \(\displaystyle N\) and \(\displaystyle M\) from the first line of the standard input. The map is found in the following \(\displaystyle N\) lines. The first and only line of the standard output should contain the minimum total length he needs to swim while visiting all islands.

Explanation. Starting from the top island he swims 1 unit down to the middle one, then 2 units to the right and reaches the lower island.

Scoring and bounds. You can get 1 point for a brief and proper documentation clearly describing your solution. Nine further points can be obtained provided that your program solves any valid input within 1 second of running time.

The source code of your program with a short documentation—also describing which developer environment to use for compiling the source—should be submitted in a compressed file s105.zip.

(10 pont)

Deadline expired on March 10, 2016.


Statistics:

8 students sent a solution.
10 points:Gáspár Attila, Mernyei Péter, Noszály Áron, Szakály Marcell.
8 points:1 student.
7 points:1 student.
6 points:1 student.
5 points:1 student.

Problems in Information Technology of KöMaL, February 2016