Elementary Graph Algorithms - Breadth First Search
Treasure Island - Problem Definition
[OOOODODOOOOOXDDO]
[OOOODODOOOOOODDOODXO]
Treasure Island - Approach
We use a variant of the BFS algorithm to find the minimum distance to reach the treasure. We maintain a FIFO queue data structure to keep discovered vertices whose adjacency list is yet to be scanned. We use an array named m to get hold of the x and y coordinate changes for each move: up, down, left and right. We have two procedures, FIND−TREASURE first calculates shortest path distances in an m⋅n matrix named d and the procedure PRINT−PATH uses this matrix in turn to print the blocks in an optimal solution. Also note that the procedure PRINT−PATH starts its job from the block where the treasure is buried, hence the treasure coordinates are passed in as an argument to the routine. The algorithms that follow describe our approach of finding the shortest path more precisely.
**Input:** Map area represented by an m⋅n matrix
**Output:** Minimum number of steps to reach the treasure along with the corresponding route.
FIND−TREASURE(G)
++ rl←G.length
++ cl←G[0].length
++ let d be a rl⋅cl matrix, each entry initialized to ∞
++ let q be an empty FIFO queue
++ let m be an array containing the finite set of moves
++ let r be the treasures row position initialized to −1
++ let c be the treasures column position initialized to −1
++ q.enqueue({0,0})
++ d[0][0]=0
++ `while` q is not empty
++ ++ u←q.dequeue()
++ ++ `for` `each` p∈m
++ ++ ++ i←u[0]+p[0]
++ ++ ++ j←u[1]+p[1]
++ ++ ++ `if` i≥0 and i<rl and j≥0 and j<cl and d[i][j]==∞ and G[i][j]≠D
++ ++ ++ ++ `if` G[i][j]==X
++ ++ ++ ++ ++ r←i
++ ++ ++ ++ ++ c=j
++ ++ ++ ++ d[i][j]←d[u[0]][u[1]]+1
++ ++ ++ ++ q.enqueue({i,j})
++ `if` r==−1 and c==−1
++ ++ throw error
++ `print` "The minimum route takes " d[r][c] " steps."
++ PRINT−PATH(d,r,c,m)
**Input:** An m⋅n matrix containing shortest path distances calculated at step 1, x and y coordinates of the treasure and the finite set of moves m.
**Output:** Shortest route to reach the treasure.
PRINT−PATH(d,i,j,m)
++ `if` i==0 and j==0
++ ++ `print` "(" i ", " j ")"
++ `else`
++ ++ r←−1
++ ++ c←−1
++ ++ s←∞
++ ++ `for` `each` p∈m
++ ++ ++ k←i+p[0]
++ ++ ++ l←j+p[1]
++ ++ ++ `if` k≥0 and k<d.length and l≥0 and l<d[0].length and d[k][l]<s
++ ++ ++ ++ r←k
++ ++ ++ ++ c←l
++ ++ ++ ++ s←d[k][l]
++ ++ `if` r==−1 and c==−1
++ ++ ++ `print` "path doesn't exist"
++ ++ `else`
++ ++ ++ PRINT−PATH(d,r,c,m)
++ ++ ++ `print` "(" i ", " j ")"
| import java.util.ArrayDeque; | |
| import java.util.Queue; | |
| class TreasureIsland { | |
| TreasureIsland() { | |
| throw new AssertionError(); | |
| } | |
| public static void main(String[] args) { | |
| final char[][] map = new char[][] { { 'O', 'O', 'O', 'O' }, { 'D', 'O', 'D', 'O' }, { 'O', 'O', 'O', 'O' }, | |
| { 'X', 'D', 'D', 'O' } }; | |
| findTreasure(map); | |
| } | |
| static void findTreasure(char[][] g) { | |
| final int rl = g.length; | |
| final int cl = g[0].length; | |
| final int[][] d = new int[rl][cl]; | |
| for (int i = 0; i < rl; i++) | |
| for (int j = 0; j < cl; j++) | |
| d[i][j] = Integer.MAX_VALUE; | |
| final Queue<int[]> q = new ArrayDeque<>(); | |
| final int[][] m = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } }; | |
| int r = -1; | |
| int c = -1; | |
| q.add(new int[] { 0, 0 }); | |
| d[0][0] = 0; | |
| while (!q.isEmpty()) { | |
| final int[] u = q.remove(); | |
| for (int[] p : m) { | |
| final int i = u[0] + p[0]; | |
| final int j = u[1] + p[1]; | |
| if (i >= 0 && i < rl && j >= 0 && j < cl && d[i][j] == Integer.MAX_VALUE && g[i][j] != 'D') { | |
| if (g[i][j] == 'X') { | |
| r = i; | |
| c = j; | |
| } | |
| d[i][j] = d[u[0]][u[1]] + 1; | |
| q.add(new int[] { i, j }); | |
| } | |
| } | |
| } | |
| if (r == -1 && c == -1) | |
| throw new IllegalArgumentException("Treasure doesn't exist or is not reachable."); | |
| System.out.println(String.format("The minimum route takes %d steps.", d[r][c])); | |
| printPath(d, r, c, m); | |
| } | |
| static void printPath(int[][] d, int i, int j, int[][] m) { | |
| if (i == 0 && j == 0) | |
| System.out.println(String.format("(%d, %d)", i, j)); | |
| else { | |
| int r = -1; | |
| int c = -1; | |
| int s = Integer.MAX_VALUE; | |
| for (int[] p : m) { | |
| final int k = i + p[0]; | |
| final int l = j + p[1]; | |
| if (k >= 0 && k < d.length && l >= 0 && l < d[0].length && d[k][l] < s) { | |
| r = k; | |
| c = l; | |
| s = d[k][l]; | |
| } | |
| } | |
| if (r == -1 && c == -1) | |
| System.out.println("path doesn't exist"); | |
| else { | |
| printPath(d, r, c, m); | |
| System.out.println(String.format("(%d, %d)", i, j)); | |
| } | |
| } | |
| } | |
| } |
Comments
Post a Comment