The board game Less is played on an 8 x 8 board with randomly placed walls betwe

Question

The board game Less is played on an 8 x 8 board with randomly placed walls between squares. Each player aims to move their pieces to the opposite comer of the board before the others do the same. We will consider a generalized single-player version of the game, where the board has size n times n. the board is specified by a positive integer n and two (n - 1) times (n - 1) Boolean arrays left Wall and bottom Wall; left Wall [i] [j] is true if there is a wall on the left edge of square (i, j) and false otherwise, bottom Wall is analogous for walls on the bottom edge of the square. Square (0, 0) corresponds to the bottom-left, and square (n - 1, n - 1) to the top-right. in one move, a player can move a piece one square horizontally or vertically if it is not blocked by a wall (see Figure 1, left). This is called a simple move. Give an algorithm that uses breadth-first-search to find the minimum number of simple moves to move a piece from the bottom-left comer of the board to the top-right. If the top-right corner is unreachable, your algorithm should return infinity. Why is your algorithm correct? Analyze the running time of your algorithm. player can also move a piece one square horizontally or vertically through a wall (see Figure 1, right). This is called a wall jump, and costs two moves. Give an algorithm that finds the minimum number of moves required to move a piece from the bottom-left comer of the board to the top-right, using both simple moves (that count as 1 move) and wall jumps (that count as 2 moves). You may use any algorithm discussed in class as a black box. Why is your algorithm correct? Analyze the running time of your algorithm. Implement your algorithm in the accompanying zip file. Every turn, each player gets three moves that they can use for any combination of simple moves or wall jumps. So during one turn, a player could perform three simple moves, a simple move followed by a wall jump, or a wall jump followed by a simple move. It is not necessary to use all three moves, so a turn could consist of just a single wall jump. Give an algorithm that finds the minimum number of three-move turns required to move a piece from the bottom-left comer of the board to the top-right, using both simple moves (that count as 1 move) and wall jumps (that count as 2 moves). You may use any algorithm discussed in class as a black box. Why is your algorithm correct? Analyze the running time of your algorithm.

Explanation / Answer

(a) move piece from bottom left to top right! this is called a grid traversal problem!! (do read more about this)

     we know that bfs always give the shortest path between two nodeS!!!!

so here we will do this as,

i) maintain 2 arrays - one for the original grid and another boolean array (say flag) to store the traversed grid points at any particular time instant.

ii)use BFS recursively. The base case is when we reach our end point or bottom corner point.When we reach our end point ,we update a global boolean flag to FALSE to indicate that no further traversal is needed(since finding one path is enough) .Every time in our recursive function we check the value of this flag to determine whether we need to continue traversal or just stop

iii) start the bfs from the bottom left

iv) initialize the flag array to true before starting the bfs.

-------------------

(b)it can be shown that bfs is an optimal and complete algorithm for path traversal when there is no extra parameters(like path cost) involved and each edge is of equally weight! so our algorithm is correct.

--------------------------

(c) the grid is basically an adjacency list! we already know that for adjacenecy list bfs has run time as O(n+m) therefore for a nXm grid, complexity for the algorithm will be O(n+m).

-------------------------------------

(d) for this unlike (a) we have to now factor in edge cost as well. use dijkstra's shortest path algorithm here!

------------------

(e) do the rest accordingly for dijkstra's

-----------------------------------------------------------------

thank you

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.