Compsci 100e, Spring 2011, Grid Recursion

Group members: name and NetID for each (max 3)
Name____________________   net-id _________       

Name____________________   net-id _________       

Name____________________   net-id _________       

You will likely want to snarf classwork-rodger/10ClwkRatRoute.

Flood-fill APTs

The Blob code above uses a recursive flood-fill algorithm for visiting all adjacent/connected nodes in a grid. The floodfill "idea" can be used to solve both the RatRoute and FloodRelief APTs.

Most APTs usually provide input parameters as an array of Strings, but your code will be easier to write if you have a two-dimensional array of characters (or ints or booleans). Here's code from a possible solution to RatRoute.java that translates the parameter into a grid; questions follow the code.

public class RatRoute {

    private char[][] myGrid;
    private int myRows, myCols;
    private int myCheeseRow, myCheeseCol;

    /**
     * Returns the number of possible routes the rat can take to get to
     * the cheese without ever increasing the distance between itself
     * and the cheese at any point on its path
     * @param enc each entry represents one row of the maze
     */
    public int numRoutes(String[] enc) {
        // initialize instance vars
        myRows = enc.length;
        myCols = enc[0].length();
        myGrid = new char[myRows][myCols];
        
        int ratRow=0,ratCol=0;
        for(int r=0; r < myRows; r++){
            Arrays.fill(myGrid[r], '.');
            for(int c=0; c < myCols; c++){
                char ch = enc[r].charAt(c);
                if (ch == 'R') {
                    ratRow = r;
                    ratCol = c; 
                }
                else if (ch == 'C') {
                    myCheeseRow = r;
                    myCheeseCol = c;
                    myGrid[r][c] = 'C'; 
                }
                else if (ch == 'X') {
                    myGrid[r][c] = 'X'; 
                }
            }
        }
        // find current distance and count # routes
        int currentDistance = cheeseDistance(ratRow,ratCol);
        return routeCount(ratRow, ratCol, currentDistance+1);
    }
  1. The nested loop initialize myGrid to be a two-dimensional array that model's the rat-maze for this problem. What's the purpose of the line Arrays.fill(myGrid[r], '.')

    1. initialize the entire grid to store a marker indicating the location hasn't been visited by the rat.

    2. identify grid locations the rat has already visited.

    3. initialize one row of the grid to store some value that's neither R,C, nor X.

  2. The variables ratRow and ratCol are not instance variables. What does this mean about accessing these values in other methods that you'll write in solving this problem?

    1. they should be passed as parameters to any method needing their values

    2. they should be stored in an anonymous inner class so they can be passed.

    3. they cannot be accessed except in numRoutes, nor can they be passed as parameters because by default they are private.

  3. Complete the method whose prototype/header is given below. The method should return the distance from a grid point to the location of the cheese using the Manhattan distance (aka taxicab geometry) formula in which distances are measured along rectilinear grid points. The distance between points (a,b) and (c,d) in this distance is |a-c| + |b-d| where absolute value is used to ensure distances are non-negative. Use Math.abs(..) to compute absolute value, use instance variables as appropriate. NOTE: The APT says to use the Euclidean distance, that also works. Use either one.

        /**
         * Returns the distance (Manhattan) from (row,col) to location of cheese
         * in the grid.
         * @param row is row coordinate
         * @param col is col coordinate
         * @return the distance from (row,col) to location of cheese
         */
        private int cheeseDistance(int row, int col) {
            // TODO: complete cheeseDistance
    
      }
    

    1. return Math.abs(row-col);

    2. return Math.abs(row-myCheeseRow + col-myCheeseCol);

    3. return Math.abs(row-myCheeseRow) + Math.abs(col-myCheeseCol);

  4. One way to develop the code to solve the APT is to write the helper method whose prototype/header follows below -- this method is called in the numRoutes code above as well:
        
        /**
         * Returns the number of ways of getting from (row,col) to cheese
         * @param lastDistance is the distance to the cheese from the location visited
         * just prior to getting to (row,col), e.g., the last cheese-distance of
         * the rat before moving to (row,col)
         */
        private int routeCount(int row, int col, int lastDistance){
            // TODO: complete routeCount
    
  5. There are four different base cases for routeCount. Describe them below. One base case occurs when row and col are outside the grid dimensions. Write code to handle this base case.

    1. if (row < 0) return 0;

    2. if (row < 0 || row >= myRows) return 0;

    3. something else (identify it)

  6. Which of the following (more than one is possible) represent a base case for which no recursive calls are made and a specific value should be returned?

    1. The location myGrid[row][col] contains an 'X', return 0

    2. The distance from (row,col) to the cheese is more than lastDistance, return 0

    3. The location myGrid[row][col] contains an 'R', return 1.

  7. There are four recursive calls needed to complete the method, be sure to accumulate the result returned by each call when you complete the APT. Describe what the calls do:
    
    
    
    
    
    

Review the FloodRelief APT.

  1. How many pumps are needed for the the following town? {"xxxxxxxxxxxxxxxxxxxxx", "xcccccccccccxxcccccxx", "xcxxxxxxxxxcxxcxxxcxx", "xcxccccccxxcxxcxxxcxx", "xcxcxcxxcxxcxxcxcxcxx", "xcccccxxcccccccxcxcxx", "ycycyyyycyycyycycycyy", "ycyccccccyycyycyyycyy", "ycyyyyyyyyycyycccccyy", "ycccccccccccyyyycyyyy", "yyyyyyycyyycyyyyccccc", "yyyyyyyycccccccycmnoc", "pqrstcccuvwxyzzcccccc"}

  2. How did you arrive at your solution?