Marching | Topcoder Archive

Problem Statement

You are country A. You are sending an army to country B by marching on land. You can start from any point in your country. Your destination can be any point in country B. Your goal is to select the shortest march and return its length. You can not march across water. You can march in any of the eight directions, orthogonally or diagonally (all directions are considered to be length=1).

The map is given as a String[] where "A" represents country A, "B" represents country B, "_"(underscore) represents land which can be marched over, and "."(period) represents water.

In the example below, A and B are on opposite ends of a small island.

"..............................."
"...AAAAAA____.......__BBBBBBB.."
".AAA..AAAAA_____.____BBBBBBBBB."
".AAAAAAAAAA_____._____________."
"...AAAAA_____._______________.."
"..............................."

Here is one possible minimal path, length 11.

"..............................."
"...AAAAAA____.......__BBBBBBB.."
".AAA..AAAAA_____._8901BBBBBBBB."
".AAAAAAAAA012345.7____________."
"...AAAAA_____.__6____________.."
"..............................."

Return the length of the shortest dry path from A to B or -1 if no such path is possible.

Definition

Class:: Marching
Method:: findDistance
Parameters:: String[]
Returns:: int
Method signature:: int findDistance(String[] map)
(be sure your method is public)

Constraints

map will contain between 1 and 50 entries inclusive.
Each entry of map will contain between 2 and 50 characters inclusive.
All entries of map will contain the same number of characters.
The character "A" will appear at least once in map.
The character "B" will appear at least once in map.
Only the characters "A", "B", ".", and "_" will appear in map.

Examples

{"...............................",
 "...AAAAAA____.......__BBBBBBB..",
 ".AAA..AAAAA_____.____BBBBBBBBB.",
 ".AAAAAAAAAA_____._____________.",
 "...AAAAA_____._______________..",
 "..............................."}

Returns: 11

The example from above.

{"A_______________.________________B",
 "________________._________________",
 "________________._________________",
 "________________._________________"}

Returns: -1

```
{"A.__.",
 "_._._",
 "___.B"}
```
```
Returns: 6
```

{"...............................",
 "...AAAAAA____.......__BBBBBBB..",
 ".AAA..AAAAA_____.____BBBBBBBBB.",
 ".AAAAAAAAAA_____._____________.",
 "...AAAAA_____.___________A___..",
 ".....B........................."}

Returns: 1

{"___.___.______.___.___.___.___.___.____.__.___.___",
 "_._._._._._.._._._._._._._._._._._._..._._._._._._",
 "_._._._._...____.___.___.___.___._.._...._._._._._",
 "_._._._.._........................_.._..._._._._._",
 "_._._._._..._____________________.._.._.._._._._._",
 "_._._._._.._....................._.._.._..__._._._",
 "_._._.__.._..___________________.._.._.._.._._._._",
 "_._._._.._.._..................._.._.._.._..._._._",
 "_._._..._.._.._________________.._.._.._.._.._._._",
 "_._._.._.._.._................._.._.._.._.._..__._",
 "_.__.._.._.._.._______________.._.._.._.._.._.._._",
 "_._.._.._.._.._..............._.._.._.._.._.._..._",
 "_..._.._.._.._.._____________.._.._.._.._.._.._._.",
 "_.._.._.._.._.._............._.._.._.._.._.._._._.",
 "_._.._.._.._.._..___________.._.._.._.._.._._._._.",
 "_._._.._.._.._.._..........._.._.._.._.._._._._._.",
 "_._._._.._.._.._.._________.._.._.._.._._._._._._.",
 "_._._._._.._.._.._........._.._.._.._._._._._._._.",
 "_._._._._._.._.._.._______.._.._.._._._._._._._._.",
 "_._._._._._._.._.._......._.._.._._._._._._._._._.",
 "_._._._._._._._.._.._____.._.._._._._._._._._._._.",
 "_._._._._._._._._.._....._.._._._._._._._._._._._.",
 "_._._._._._._._._._..___.._._._._._._._._._._._._.",
 "_._._._._._._._._._._..._._._._._._._._._._._._._.",
 "_._._._._._._._._._._.A._._._._._._._._._._._._._.",
 "_._._._._._._._._._._._.B._._._._._._._._._._._._.",
 "_._._._._._._._._._._._..._._._._._._._._._._._._.",
 "_._._._._._._._._._._..___.._._._._._._._._._._._.",
 "_._._._._._._._._._.._....._.._._._._._._._._._._.",
 "_._._._._._._._._.._.._____.._.._._._._._._._._._.",
 "_._._._._._._._.._.._......._.._.._._._._._._._._.",
 "_._._._._._._.._.._.._______.._.._.._._._._._._._.",
 "_._._._._._.._.._.._........._.._.._.._._._._._._.",
 "_._._._._.._.._.._.._________.._.._.._.._._._._._.",
 "_._._._.._.._.._.._..........._.._.._.._.._._._._.",
 "_._._.._.._.._.._..___________.._.._.._.._.._._._.",
 "_._.._.._.._.._.._............._.._.._.._.._.._.._",
 "_.._.._.._.._.._.._____________.._.._.._.._.._.._.",
 "._.._.._.._.._.._..............._.._.._.._.._.._..",
 "___.._.._.._.._.._______________.._.._.._.._..____",
 "_....._.._.._.._................._.._.._.._......_",
 "_____.._.._.._.._________________.._.._.._..______",
 "....._.._.._.._..................._.._.._.._......",
 "_______.._.._..___________________.._.._..________",
 "_........._.._....................._.._.........._",
 "_________.._.._____________________.._..__________",
 "........._.._......................._.._..........",
 "___________.._______________________..____________",
 "_................................................_",
 "__________________________________________________"}

Returns: 1073

```
{"AB"}
```
```
Returns: 1
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.