I have looked through many forum codes which are similar to this question, but I am still unable to solve my question. Basically, given a 2D square array of size n, filled with integers within [-100,100], I have to find the maximum sum, given that the path is of length 10. This is done starting from a certain given grid (denoted by *). It is illegal to visit a same grid twice.
A sample test case would be:
-55 34 -51 35 1
-76 26 69 61 *
68 98 17 85 81
-27 -69 49 42 83
-10 31 44 75 -41
Would produce a maximum sum of 637.
Denoted by the path: 61 69 26 98 17 85 81 83 42 75
If I'm not wrong, the problem with my code is about marking the grids that I have visited before. But I don't know how to solve that..
Below is my code:
import java.util.*;
class Maze
{
static int[][] matrix;
static int counter = 0;
static int size = 0;
static int maximum = -100000;
static int result = -1000000;
static int currMax;
static int topMax, downMax, leftMax, rightMax;
public static void main(String [] args)
{
Scanner sc = new Scanner(System.in);
size = sc.nextInt();
matrix = new int[size][size];
int xcord = 0;
int ycord = 0;
for (int i=0; i<size; i++){
for (int j=0; j<size; j++){
if (sc.hasNextInt()){
int util = sc.nextInt();
matrix[i][j] = util;
}
else{
String utilStr = sc.next();
xcord = i;
ycord = j;
matrix[i][j] = -2000;
}
}
}
result = 2000 + findMax(xcord, ycord);
System.out.println(result);
}
static int findMax(int currx, int curry){
if (counter >= 9){
return matrix[currx][curry];
}
else {
counter = counter+1;
System.out.println("Round: "+counter);
System.out.println("currx: "+currx+" curry: "+curry);
int temp = matrix[currx][curry];
matrix[currx][curry] = -2000;
downMax = -10000; //To reset it for comparison
if (currx+1 != size && matrix[currx+1][curry] == -2000){
downMax = findMax(currx+1,curry);
}
rightMax = -10000;
if (curry+1 != size && matrix[currx][curry+1] == -2000){
rightMax = findMax(currx,curry+1);
}
topMax = -10000;
if (currx-1 >=0 && matrix[currx-1][curry] == -2000){
topMax = findMax(currx-1,curry);
}
leftMax = -10000;
if (curry-1 >= 0 && matrix[currx][curry-1] == -2000){
leftMax = findMax(currx,curry-1);
}
matrix[currx][curry] = temp;
currMax = Math.max(downMax,rightMax);
currMax = Math.max(currMax, topMax);
currMax = Math.max(currMax, leftMax);
maximum = currMax + temp;
return maximum;
}
}
}
Thanks in advance!!
Here is my solution and explanations:
public static int MAX_DEPTH = 10;
static Integer[][] matrix;
static Coord[] directions = {
new Coord(-1, 0),
new Coord(1, 0),
new Coord(0, -1),
new Coord(0, 1)
};
private static class Coord {
int row;
int col;
private Coord(int row, int col) {
this.col = col;
this.row = row;
}
private Coord newPosition(Coord relative) {
return new Coord(row + relative.row, col + relative.col);
}
}
First, I define the matrix as a 2D array of Integer rather than int. This makes it easy to mark visited positions and the "*" position using null. It's just a convenience.
I am using a small inner class Coord to help me with coordinate calculations. As you see, I have created a static array of all the directions I'll need to explore at every step, as this will simplify the recursive method, and prevent unneeded repetitions of code that may later need fixing in four different places.
private static Coord fillMatrix() {
Scanner sc = new Scanner(System.in);
int size = sc.nextInt();
matrix = new Integer[size][size];
Coord coord = new Coord(0, 0);
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (sc.hasNextInt()) {
int util = sc.nextInt();
matrix[i][j] = util;
} else {
sc.next();
coord.row = i;
coord.col = j;
matrix[i][j] = null;
}
}
}
sc.close();
return coord;
}
My fillMatrix method fills the matrix and returns the coordinate of the "*" (or rather, the non-integer in the input). It's based on yours, with these notes:
private static boolean isLegalPosition(Coord position) {
if ( position.row < 0 || position.row >= matrix.length ) {
return false;
}
if ( position.col < 0 || position.col >= matrix[0].length ) {
return false;
}
return matrix[position.row][position.col] != null;
}
Given a position in the matrix, this method checks if it is legal - if it is within the boundaries of the arrays (we have to assume at least one row exists), and if it is not marked with a null (visited/start).
Now we come to the recursive method itself. You pass it the current depth and the current accumulated sum, in addition, of course, to the current position from which it should start looking. This position is assumed to already be marked with null.
private static Integer findMax(Coord currPosition, int currDepth,
int currSum) {
// Recursion end: if we reached a depth of 10, we have the maximum at
// the current position
if (currDepth == MAX_DEPTH) {
return currSum;
}
// Find the greatest number in all four directions. We start with an
// unknown Max value.
Integer currMax = null;
for (Coord direction : directions) {
Coord newPos = currPosition.newPosition(direction);
// If the position is legal (inside the matrix and not visited),
// explore it by adding depth, and adding the current matrix
// value to the accumulated.
if (isLegalPosition(newPos)) {
// Save the value at the new position, and mark it as visited.
int matrixValue = matrix[newPos.row][newPos.col];
matrix[newPos.row][newPos.col] = null;
Integer newMax = findMax(newPos, currDepth + 1, currSum + matrixValue);
// Restore the value in the current matrix position so that
// upper level recursions don't think it's visited.
matrix[newPos.row][newPos.col] = matrixValue;
// Calculate the new max. If this is the first legal path, use
// it. Otherwise check which one is greater.
if (newMax != null) {
currMax = (currMax == null) ? newMax
: (newMax > currMax ? newMax : currMax);
}
}
}
return currMax;
}
As you can see, I keep a variable named currMax, which starts out as null. It will end up being the max among all numbers collected from the four directions. But it may happen that all four directions could not reach depth 10 because they run into the wall and visited positions. In that case, they will return null, and if this happens in all four directions, we return currMax - which is null - as well.
If we do find a legal path in any of the directions, we'll update currMax with it (if it's greater than it, of course).
At each step, before we go deeper into the recursion, we mark the new position with null to show it was visited, but take care to restore it as soon as we finish with it. Otherwise the position will stay marked for the visit of the next direction, for which it is not supposed to be considered visited.
The call to the recursion from main, after filling the matrix, of course, looks like this:
Integer maxVal = findMax(startCoord, 0, 0);
That is, we pass it the coordinates of the "*", start at the depth of 0, and with an accumulated sum of 0. Why 0 and not -2000? Because we are not actually comparing this number with anything. Any path we go through which actually gets to depth 10 will return the actual sum of the positions it has traversed, added to this zero, whether this sum is negative or positive. Any path that doesn't end up at depth 10 will return null. So no need for artificial values.