UVa 10937

From Algorithmist
Jump to: navigation, search

10937 - Blackbeard the Pirate[edit]

Summary[edit]

Arrrgh! T' problem be a simple Traveling Salesperson Problem, where you can improve upon it with Dynamic Programming, but not necessary for this particular problem. You will need to use a search algorithm (preferably Breadth-First Search) to calculate the distances between the treasures and the starting location.

Explanation[edit]

First, you'll need to calculate the distances between the crucial points, using Breadth-First Search and making sure carefully that the constraints are satisfied. After we get the distances, the rest is a straightforward bruteforce Traveling Salesperson Problem, which can you speed it up with Memoization.

Input[edit]

7 7
~~~~~~~
~#!###~
~...#.~
~~....~
~~~.@~~
.~~~~~~
...~~~.
10 10
~~~~~~~~~~
~~!!!###~~
~##...###~
~#....*##~
~#!..**~~~
~~....~~~~
~~~....~~~
~~..~..@~~
~#!.~~~~~~
~~~~~~~~~~
3 3 
*@. 
... 
..!
3 3 
... 
.@. 
...
5 5
!!!!!
@....
.....
.....
.....
1 9
!!!!@!!!!
3 3
..*
@!.
...
5 5
..!..
.....
*****
.....
@....

Output[edit]

10
32
-1
0
10
16
-1
-1