Name____________________ net-id _________ Name____________________ net-id _________ Name____________________ net-id _________You will likely want to snarf classwork-rodger/10ClwkRatRoute.
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); }
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],
'.')
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?
numRoutes
, nor
can they be passed as parameters because by default they
are private.
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 }
return Math.abs(row-col);
return Math.abs(row-myCheeseRow + col-myCheeseCol);
return Math.abs(row-myCheeseRow) + Math.abs(col-myCheeseCol);
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
routeCount
. Describe them below. One base case
occurs when row
and col
are
outside the grid dimensions. Write code to handle this base
case.
if (row < 0) return 0;
if (row < 0 || row >= myRows) return 0;
myGrid[row][col]
contains an 'X', return
0
(row,col)
to the cheese is more
than
lastDistance
, return 0
myGrid[row][col]
contains an 'R',
return 1.
Review the FloodRelief APT.