- #1
frankfjf
- 168
- 0
Homework Statement
"Write a recursive Java program that finds the longest increasing sequence in a two-dimensional grid of numbers. A sequence is simply a series of adjacent squares. Squares may not be used twice. A grid might have multiple longest sequences. If an input grid does have multiple longest subsequences, your program should display only one such subsequence."
Homework Equations
Example: In the following grid:
97 47 56 36 60 31 57 54 12 55
35 57 41 13 82 80 71 93 31 62
89 36 98 75 91 46 95 53 37 99
25 45 26 17 15 82 80 73 96 17
75 22 63 96 96 36 64 31 99 86
12 80 42 74 54 14 93 17 14 55
14 15 20 71 34 50 22 60 32 41
90 69 44 52 54 73 20 12 55 52
39 33 25 31 76 45 44 84 90 52
94 35 55 24 41 63 87 93 79 24
the longest increasing sequence has length 10, consisting of entries (r,c) (row and column, starting at zero) as follows:
(5,0) with value 12
(6,0) with value 14
(6,1) with value 15
(6,2) with value 20
(7,2) with value 44
(7,3) with value 52
(7,4) with value 54
(6,3) with value 71
(5,3) with value 74
(4,3) with value 96
The Attempt at a Solution
Here is my program thus far, hopefully not too messy:
Code:
public class gridRunner
{
public static int testGrid[][] = {{97, 47, 56, 36, 60, 31, 57, 54, 12, 55}, {35, 57, 41, 13, 82, 80, 71, 93, 31, 62},
{89, 36, 98, 75, 91, 46, 95, 53, 37, 99}, {25, 45, 26, 17, 15, 82, 80, 73, 96, 17},
{75, 22, 63, 96, 96, 36, 64, 31, 99, 86}, {12, 80, 42, 74, 54, 14, 93, 17, 14, 55},
{14, 15, 20, 71, 34, 50, 22, 60, 32, 41}, {90, 69, 44, 52, 54, 73, 20, 12, 55, 52},
{39, 33, 25, 31, 76, 45, 44, 84, 90, 52}, {94, 35, 55, 24, 41, 63, 87, 93, 79, 24}};
public static void main(String[] args)
{
System.out.println(getMaxPath(1, 5, 0));
}
public static String getMaxPath(int startL, int r, int c)
{
String maxPath = "\n(" + r + "," + c + ") with value " + testGrid[r][c];
int length = startL;
if (checkBounds(r - 1, c)) //check North
{
if (testGrid[r][c] < testGrid[r - 1][c])
{
length++;
return maxPath += getMaxPath(length, r - 1, c);
}
}
if (checkBounds(r - 1, c + 1)) //check Northeast
{
if (testGrid[r][c] < testGrid[r - 1][c + 1])
{
length++;
return maxPath += getMaxPath(length, r - 1, c + 1);
}
}
if (checkBounds(r, c + 1)) //check East
{
if (testGrid[r][c] < testGrid[r][c + 1])
{
length++;
return maxPath += getMaxPath(length, r, c + 1);
}
}
if (checkBounds(r + 1, c + 1)) //check Southeast
{
if (testGrid[r][c] < testGrid[r + 1][c + 1])
{
length++;
return maxPath += getMaxPath(length, r + 1, c + 1);
}
}
if (checkBounds(r + 1, c)) //check South
{
if (testGrid[r][c] < testGrid[r + 1][c])
{
length++;
return maxPath += getMaxPath(length, r + 1, c);
}
}
if (checkBounds(r + 1, c - 1)) //check Southwest
{
if (testGrid[r][c] < testGrid[r + 1][c - 1])
{
length++;
return maxPath += getMaxPath(length, r + 1, c - 1);
}
}
if (checkBounds(r, c - 1)) //check West
{
if (testGrid[r][c] < testGrid[r][c - 1])
{
length++;
return maxPath += getMaxPath(length, r, c - 1);
}
}
if (checkBounds(r - 1, c - 1)) //check Northwest
{
if (testGrid[r][c] < testGrid[r - 1][c - 1])
{
length++;
return maxPath += getMaxPath(length, r - 1, c - 1);
}
}
return maxPath + "\nGreatest path is of length " + length + ".";
}
public static boolean checkBounds(int r, int c)
{
if ((r >= 0 && r <= 9) && (c >= 0 && c <= 9))
return true;
return false;
}
}
However, this does not produce the result obtained in the example. What can I do to cause my recursive method to find the longest path correctly that I am currently not doing in the code? Also, should the starting coordinates matter?