Recitation 6: Flood Fill

February 21, 2013

For this recitation you will submit answers to the below questions using this submision form.

In class we discussed the flood-fill algorithm for visiting all adjacent/connected nodes in a grid.

In the coming week you'll do these APTs: RatRoute, NumberFill, and FloodRelief which all use variations on the flood-fill algorithm.

RatRoute

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 that translates the RatRoute parameter into a grid; questions follow the code, and your answers should be submitted using the submision form

public class RatRoute { private char[][] myGrid; private int myRows, myCols ; private int myCheeseRow, myCheeseCol; public int numRoutes(String[] enc){ myRows = enc.length; myCols = enc[0].length(); myGrid = new char[myRows][myCols]; // initialize instance vars 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], '.') and how could you use another else if in the chain of code assigning values to myGrid in place of it?

2. Our convention at Duke (and used in other places as well) is that instance variables begin with the prefix my. What are the names and purposes of the five instance variables in the program (reason as best you can given the names)?

3. 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?

4. Write a 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.

     /**
      * 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) {
   
   
     }
   

5. 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){ if (row < 0 || col < 0 || row >= myRows || col >= myCols) return 0; if (myGrid[row][col] == 'C') return 1; if (myGrid[row][col] == 'X') return 0; // more code here
   1. What is the purpose of the first if statement, returning zero?

   2. What is the purpose of the second if statement, returning one?

   3. What is the purpose of the third if statement, returning zero?

   4. The code above handles several base-cases (no recursive calls), but one more base case must be considered: the case that the rat has moved to (row,col) and away from the cheese. Before moving to (row,col) the distance from the cheese is the value of parameter lastDistance (read the comments carefully). Write code to handle the base case when the rat has moved farther from the cheese and thus there are no routes to the cheese by writing code here:

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