# UVa 10937

Jump to navigation
Jump to 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