Computer Science

Graph Algorithms

Graph Algorithms: Level 3 Challenges


Harry is going out on a date with Megan. He is planning out the situations he might face.

What algorithm is he employing to search through the possibilities​?

Relevant algorithms:

Image Credit: xkcd 761.

Sally is a very bad skater, so she can only skate in one direction! But Sally still wants to find her dad in the least amount of moves possible so that she can get off the ice. Sally's only way of stopping is (crashing into) walls or the edge of the ice rink.

We describe the ice rink using the following notation:

(#) -- Wall
(.) -- Free space
(S) -- Sally's starting position
(D) -- Dad's position.

For example, in the ice rink at right, the shortest path is 18 steps.

Here is a text file of 5 ice rinks of size 20×20 20 \times 20 . The rinks are separated by hyphens.

Find the sum of the shortest paths of these five 20×20 20 \times 20 ice rinks.

Note: Sally has to stop at her father's position. She will slide past him if there are no walls.

Image credit: Flickr Saad Akhtar

What data structure should be used so that Dijkstra shortest path algorithm on unweighted graphs runs in linear time?


Problem Loading...

Note Loading...

Set Loading...