import java.util.*;

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);
    }
    
    /**
     * 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 0;
    }
    
    /**
     * 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 add base cases
        // TODO: complete routeCount
        return 0;
    }
}