Consider a grid of nxn grid of integers like the following: 2 3 2 1 1 2 2 3 2 1

Question

Consider a grid of nxn grid of integers like the following:

2 3 2 1

1 2 2 3

2 1 1 2

3 1 2 3

In this grid, you may only move in four directions from one square to another: up, down, left and right. But, the number of the square you move from must be less than or equal to the number of the square you are moving to. Write a recursive method that determines whether or not there is a path from a starting square to an ending square. To help with this task, an auxiliary boolean array will be given as an input parameter. Each location in this array signifies whether or not a particular square has been "visited" yet. (Sorry about the poor object-oriented design. I didn't want to have to take the time to design a class with an object, etc. just for this question.)

// (startx, starty) is the row and column of the starting

// location in the grid and is guaranteed to be valid.

// (endx, endy) is the row and column of the destination

// on the grid and is also guaranteed to be valid.

// visited is the same size as board and stores true in

// an element if that particular square has been reached

// from the starting destination. The method should

// originally be called with visited storing all falses.

public static boolean canMove(int[][] board, int startx,

int starty, int endx,

int end y,

boolean[][] visited);

Explanation / Answer

In case the code does not look formatted, then just insert a newline character(enter) in place of every newline comment. public static boolean canMove(int[][] board, int startx, int starty, int endx, int endy,boolean[][] visited){ //newline boolean up,down,left,right; //newline boolean b1=false,b2=false,b3=false,b4=false; //newline if(startx == endx && starty == endy) return true;//base case //newline /**Check whether it is feasible move in a direction * It is feasible to move in a direction if and only if the square to be * visited has not been visited yet and the square to be visited has a value * greater than or equal to the value of current square **/ //newline up = !visited[startx - 1][starty] && board[startx - 1][starty] >= board[startx][starty]; //newline down = !visited[startx + 1][starty] && board[startx + 1][starty] >= board[startx][starty];//newline left = !visited[startx][starty - 1] && board[startx][starty - 1] >= board[startx][starty];//newline right = !visited[startx][starty + 1] && board[startx][starty + 1] >= board[startx][starty];//newline /** Recursively find if the end square can be visited * from the next square where we are moving to */ //newline if(up){//newline visited[startx][starty] = true; //newline b1 = canMove(board, startx - 1, starty, endx, endy, visited); //newline }//newline if(down){ //newline visited[startx][starty] = true; //newline b2 = canMove(board, startx + 1, starty, endx, endy, visited); //newline } //newline if(left){ //newline visited[startx][starty] = true; //newline b3 = canMove(board, startx, starty - 1, endx, endy, visited); //newline }// newline if(right){ //newline visited[startx][starty] = true; /newline b4 = canMove(board, startx, starty +1, endx, endy, visited); //newline } //newline /** If a path to the end square exists from any of the squares which can be * visited from this current square, then the path to end square * exists from this square also */ //newline return b1||b2||b3||b4; //new line }

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.