// ITI 1120 Fall 2007, Assignment 4, Question 3// Name: , Student# - Please complete with your student information.import java.io.*;import javax.swing.JOptionPane;/** * Library class for find a path within a boolean matrix (N x M) * Please complete the methods. * File A4Q3Test.java provides a set of JUnit tests for testing * each of the methods (both findPath and doPath are tested together) */class A4Q3{ public static void main (String[] args) { //testing purposes int[][] path; path = new int[3][2]; path[0][0] = 0; path[0][1] = 1; path[1][0] = 1; path[1][1] = 1; boolean[][] grid; grid = new boolean[4][5]; grid[0][0] = false; grid[0][1] = true; grid[0][2] = false; grid[0][3] = false; grid[0][4] = false; //next row grid[1][0] = false; grid[1][1] = true; grid[1][2] = false; grid[1][3] = false; grid[1][4] = false; //next row grid[2][0] = false; grid[2][1] = true; grid[2][2] = true; grid[2][3] = false; grid[2][4] = false; //next row grid[3][0] = false; grid[3][1] = true; grid[3][2] = false; grid[3][3] = false; grid[3][4] = false; //next row path = doPath(grid, path); }//end main method // It all starts here. Calling the following method will have it return // an integer matrix consisting of a list of points that defines a // path of true values in the Boolean matrix. The row and col parameters // provide the first point in the path that lies on the border of the matrix. // (Hint: this method should be very simple since it will call doPath to // do all the real work. public static int [] [] findPath(boolean [][] grid, int row, int col) { return(new int[][] { {0,0} }); } // This is the method that does the real work of finding the path. But // it does use other methods in this class to make its code much simpler // clearer and easier to debug. Note that, the end of the path is found when // 1) The point returned by findNextPoint is on the border of the grid matrix // 2) A null is returned by findNextPoint public static int [] [] doPath(boolean [][] grid, int [][] path) { //Alright so the path matrix that is passed to this method will only have one point //that is, the original border point. //we want to find the next point, and then add this point to the path matrix, and continue to do this until //the point returned by findNextPoint isonBorder or null. int[] NextPoint = new int[2]; //we need to test whether or not this point is on the border. if it is we must exit our loop boolean on_border = false; int[][] new_path; new_path = new int[2][2]; while (on_border == false) { NextPoint = findNextPoint(grid,path); int row = NextPoint[0]; int col = NextPoint[1]; on_border = isOnBorder(grid, row, col); new_path = addPoint(path, row, col); } return(new_path); } // This method tries to find the next point in a path partially built. // The parameter path provides the list of points found so far. The last // point found can be found at the end of the path parameter. The row // and column number of then next point is returned in an integer array // of length 2. If no next point can be found or more than one next point // exists, then a null is returned. public static int [] findNextPoint(boolean [][] grid, int [][] path) { //first lets find out where we are at in the path. int Pointfound = 0; int[] CurrentPoint = new int[2]; CurrentPoint[0] = path[(path.length-1)][0]; CurrentPoint[1] = path[(path.length-1)][1]; //now let us find out the previous point from which we came from. We need to know this as we will be comparing //all the values of the other points to decide where the nextpoint is.. we don't want to move back to where we //came from. int[] PreviousPoint = new int[2]; PreviousPoint[0] = path[(path.length-2)][0]; PreviousPoint[1] = path[(path.length-2)][1]; int[] NextPoint = new int[2]; //This if statement checks the point to the right of our current point, and if it is true and not equal to //the previous point, then it is our next point. The other three if statements do the same thing- except //to the left, up and down instead of to the right. if((grid[CurrentPoint[0]][(CurrentPoint[1]+1)] == true) && ((CurrentPoint[0] != PreviousPoint[0]) || ((CurrentPoint[1]+1) != PreviousPoint[1]))){ //testing purposes System.out.println("The point has been found, and it is to the right"); NextPoint[0] = CurrentPoint[0]; NextPoint[1] = (CurrentPoint[1]+1); Pointfound++; } //to the left if((grid[CurrentPoint[0]][(CurrentPoint[1]-1)] == true) && ((CurrentPoint[0] != PreviousPoint[0]) || ((CurrentPoint[1]-1) != PreviousPoint[1]))){ //testing purposes System.out.println("The point has been found, and it is to the left"); NextPoint[0] = CurrentPoint[0]; NextPoint[1] = (CurrentPoint[1]-1); Pointfound++; } //above if((grid[(CurrentPoint[0]-1)][CurrentPoint[1]] == true) && (((CurrentPoint[0]-1) != PreviousPoint[0]) || (CurrentPoint[1] != PreviousPoint[1]))){ //testing purposes System.out.println("The point has been found, and it is above"); NextPoint[0] = (CurrentPoint[0]-1); NextPoint[1] = CurrentPoint[1]; Pointfound++; } //below if((grid[(CurrentPoint[0]+1)][CurrentPoint[1]] == true) && (((CurrentPoint[0]+1) != PreviousPoint[0]) || (CurrentPoint[1] != PreviousPoint[1]))){ //testing purposes System.out.println("The point has been found, and it is below"); NextPoint[0] = (CurrentPoint[0]+1); NextPoint[1] = CurrentPoint[1]; Pointfound++; } //thats it! since the path cannot move diagonally, we are done finding out the next point. //we must check to see if no points are found or if multiple points are found. If so we return an empty array. //testing purposes: System.out.println("Pointfound: " + Pointfound); if((Pointfound > 1) || (Pointfound == 0)){ return(null); } else{ return(NextPoint); } } // The addPoint method appends the given row and column numbers (row and col) // to the end of the path list (defined in the matrix path). Note that it // is necessary to create a new matrix with a additional row to // store the given row and column numbers. The reference to the new // matrix is returned by the method. public static int [][] addPoint(int [][] path, int row, int col) { //increase the row length by one int new_row_length = path.length + 1; //always 2 columns //create the new matrix int[][] new_matrix; new_matrix = new int[new_row_length][2]; int i = 0; //the following while loop copies out the existing path matrix to the new matrix while (i <= (path.length - 1)){ new_matrix[i][0] = path[i][0]; new_matrix[i][1] = path[i][1]; i++; } //the next bit of code addds whatever is in row and col to a row at the bottom of the new matrix. new_matrix[path.length][0] = row; new_matrix[path.length][1] = col; //thats it! return(new_matrix); } // This method returns true if the point in the matrix defined // by the given row and column numbers(row and col parameters) // is on the border of the matrix (first/last row or first/last column) // and false otherwise. public static boolean isOnBorder(boolean [][] matrix, int row, int col) { int row_length = matrix.length; int col_length = matrix[0].length; boolean flag = false; //this is set to true when we are on a border. /*we are given a point (row,col) in the matrix and we want to know if it lies on the border. ie we want to know if row is equal to the first row or the last row or if col is equal to the first column or last column*/ //row_length-1 is the last row since the rows start at zero, same with col. if((row == (row_length - 1)) || (row == 0)){ flag = true; } if((col == (col_length - 1)) || (col == 0)){ flag = true; } if((flag == true)){ return(true); } else{ return(false); } }//end isOnBorder method}//end class