Skip to content

Instantly share code, notes, and snippets.

@Dicee
Last active October 4, 2015 21:34
Show Gist options
  • Save Dicee/9826814ac6845627a3d1 to your computer and use it in GitHub Desktop.
Save Dicee/9826814ac6845627a3d1 to your computer and use it in GitHub Desktop.
package stackoverflow;
import java.util.Scanner;
public class MatrixTraversal {
static int[][] cost;
static int m, n, maxCost = 0;
public static void solve(int currRow, int currCol, int[][] isVisited, int currCost) {
int upperRow, lowerRow, rightCol;
isVisited[currRow][currCol] = 1; //marking current position in in matrix as visited
currCost += cost[currRow][currCol]; //total cost upto current position
if( currCol == (n - 1) //if we have reached the last column in matrix
&& maxCost < currCost ) //and present cost is greater than previous maximum cost
maxCost = currCost;
upperRow = ((currRow - 1) + m) % m; //upper row value taking care of teleportation
lowerRow = (currRow + 1) % m; //lower row value taking care of teleportation
rightCol = currCol + 1; //right column value
if( isVisited[upperRow][currCol] == 0 ) //if upper cell has not been visited
solve(upperRow, currCol, isVisited, currCost);
if( isVisited[lowerRow][currCol] == 0 ) //if lower cell has not been visited
solve(lowerRow, currCol, isVisited, currCost);
if( rightCol != n && //if we are not at the last column of the matrix
isVisited[currRow][rightCol] == 0 ) //and the right cell has not been visited
solve(currRow, rightCol, isVisited, currCost);
isVisited[currRow][currCol] = 0;
}
public static void main(String[] args) {
int[][] isVisited;
int i, j;
Scanner sc = new Scanner(System.in);
System.out.print("Enter the no.of rows(m): ");
m = sc.nextInt();
System.out.print("Enter the no.of columns(n): ");
n = sc.nextInt();
cost = new int[m][n];
isVisited = new int[m][n];
System.out.println("Enter the cost matrix:");
for(i = 0; i < m; i++)
for(j = 0; j < n; j++)
cost[i][j] = sc.nextInt(); //generating the cost matrix
for(i = 0; i < m; i++)
solve(i, 0, isVisited, 0); //finding maximum traversal cost starting from each cell in 1st column
System.out.println(maxCost);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment