/** Lab 05: predict each result before running. */ public class MazePractice { /** * Task 6 check: runs the frontier loop with a Stack, prints the first * {@code count} cells removed, then draws the grid. There is no target; * this only shows ORDER. Run it only after you have finished your hand trace. */ public static void printStackOrder(Maze maze, Cell start, int count) { maze.reset(); int[][] removedAt = new int[maze.getRows()][maze.getCols()]; // step each cell was removed (0 = not yet) Stack frontier = new LinkedList(); start.setPrev(start); // the start marks itself discovered frontier.push(start); System.out.print("Stack order:"); for (int step = 0; step < count && frontier.size() > 0; step++) { Cell cur = frontier.pop(); // newest discovered cell first removedAt[cur.getRow()][cur.getCol()] = step + 1; System.out.print(" (" + cur.getRow() + "," + cur.getCol() + ")"); for (Cell n : maze.getNeighbors(cur)) { if (n.getPrev() == null) { // undiscovered? n.setPrev(cur); // mark when ADDED, not when removed frontier.push(n); } } } System.out.println(); printGrid(maze, removedAt); } /** * Task 6 check: the same loop with a Queue frontier. * TODO: Copy the body of printStackOrder, then change ONLY what the * frontier needs. Print "Queue order:" instead of "Stack order:". * Keep the removedAt and printGrid lines, so your grid prints too. * Make a list of every line you changed; you will need it in Project 05. */ public static void printQueueOrder(Maze maze, Cell start, int count) { // TODO } /** * Provided: draws the maze as a grid, one cell per column. * S = the start (always the first cell removed) * number = the step at which that cell was removed from the frontier * * = discovered (marked and waiting in the frontier), not yet removed * . = not discovered * X = obstacle * Rows go down the page and columns go across, so (1,0) is row 1, column 0. */ public static void printGrid(Maze maze, int[][] removedAt) { System.out.print(" "); for (int c = 0; c < maze.getCols(); c++) System.out.printf("%3s", "c" + c); System.out.println(); for (int r = 0; r < maze.getRows(); r++) { System.out.printf("%-5s", "r" + r); for (int c = 0; c < maze.getCols(); c++) { Cell cell = maze.get(r, c); String mark; if (cell.getType() == CellType.OBSTACLE) mark = "X"; else if (removedAt[r][c] == 1) mark = "S"; else if (removedAt[r][c] > 0) mark = "" + removedAt[r][c]; else if (cell.getPrev() != null) mark = "*"; else mark = "."; System.out.printf("%3s", mark); } System.out.println(); } System.out.println(" (S = start, number = removal step, * = waiting in frontier, . = undiscovered)"); System.out.println(" No target: this shows only the order cells are explored."); System.out.println(); } public static void main(String[] args) { // Task 5: the Maze and Cell classes Maze maze = new Maze(3, 5, 0.0); System.out.println(maze); System.out.println("Corner neighbors: expected 2, got " + maze.getNeighbors(maze.get(0, 0)).size()); // TODO: Print the actual corner neighbors using a for-each loop. // TODO: Predict and check an interior cell's neighbors, including their order. // TODO: Block one of those neighbors; predict and check the new result. // TODO: Print the maze again. Which row and column is your X in? // TODO: Set a FREE cell's prev, then call reset. Verify prev becomes null // and that your obstacle remains an obstacle. // Task 6: finish BOTH hand traces before running these lines. Maze grid = new Maze(3, 3, 0.0); printStackOrder(grid, grid.get(1, 1), 4); printQueueOrder(grid, grid.get(1, 1), 4); } }