Login or Create an Account to view the mark scheme, comment, and add to a test
HexaQuesta is a game played on a board that is divided into hexagonal regions. There are three kinds of borders between regions:
• Normal borders take one move to cross.
• River borders take two moves to cross.
• Mountain borders cannot be crossed.
Game boards may contain thousands of hexagonal regions.
The objective of the game is to travel across the board from the start, S, to the finish, X, with the fewest number of moves possible.
Samarth would like to write a program that determines how to win the game.
(a).
Describe an ADT that appropriately models a board of the HexaQuesta game.
[2](b).
Write an algorithm, in pseudocode, that Samarth could use to efficiently find a winning path from the start to the finish on any board.
[5](c).
Samarth would like to find the best starting region on a given board. He decides that the best starting region is the one with the lowest average number of moves to travel to every other region on the board.
[3]Describe how Samarth could efficiently find the best starting region on the board and derive a running time for your solution. Do not provide pseudocode in your answer.
Extended Response10 MarksShared
0 Uses1 View0 Likes