有二维数组long[50][50]
,它是从0到100的随机数填充的。我需要找到从最大(或第一个最高)到最小的最长路径。你可以向上,向下,向左和向右移动。从最大到最小的二维数组中的最长路径
我发现如何找到单一的方式:找到最大的最接近的数字(但没有更大,它是),并在那里移动。
public static int measure = 50;
public long[][] map = new long[measure][measure];
我的移动方法:
private long moveUp(int x, int y) {
if (x >= measure || x == 0 || y == 0 || y >= measure) {
return -1;
}
return map[x - 1][y];
}
private long moveRight(int x, int y) {
if (x >= measure || x == 0 || y == 0 || y >= measure) {
return -1;
}
return map[x][y + 1];
}
private long moveDown(int x, int y) {
if (x >= measure || x == 0 || y == 0 || y >= measure) {
return -1;
}
return map[x + 1][y];
}
private long moveLeft(int x, int y) {
if (x >= measure || x == 0 || y == 0 || y >= measure) {
return -1;
}
return map[x][y - 1];
}
查找最近的最大:
private long rightWay(int x, int y) {
List<Long> pickList = new ArrayList<>();
long up = moveUp(x, y);
long right = moveRight(x, y);
long down = moveDown(x, y);
long left = moveLeft(x, y);
if (up != -1 && up < map[x][y]) {
pickList.add(moveUp(x, y));
}
if (right != -1 && right < map[x][y]) {
pickList.add(moveRight(x, y));
}
if (down != -1 && down < map[x][y]) {
pickList.add(moveDown(x, y));
}
if (left != -1 && left < map[x][y]) {
pickList.add(moveLeft(x, y));
}
if (pickList.size() == 0) {
return -1;
} else {
Collections.sort(pickList);
for (int i = 0; i < pickList.size(); i++) {
System.out.println("right way " + i + " -> " + pickList.get(i));
}
return pickList.get(pickList.size() - 1);
}
}
然后发现仅使用最接近最大值最长的方式:和尺寸
private void findRoute(long[][] route, long current, int width, int height) {
System.out.println("width = " + width + " height = " + height);
long nextSpetHeight = rightWay(width, height);
System.out.println("max = " + nextSpetHeight);
if (nextSpetHeight == -1) {
return;
} else {
if (nextSpetHeight == moveUp(width, height)) {
findRoute(route, nextSpetHeight, width - 1, height);
way.add(nextSpetHeight);
}
if (nextSpetHeight == moveRight(width, height)) {
findRoute(route, nextSpetHeight, width, height + 1);
way.add(nextSpetHeight);
}
if (nextSpetHeight == moveDown(width, height)) {
findRoute(route, nextSpetHeight, width + 1, height);
way.add(nextSpetHeight);
}
if (nextSpetHeight == moveLeft(width, height)) {
findRoute(route, nextSpetHeight, width, height - 1);
way.add(nextSpetHeight);
}
}
}
way
wo这是该路线的长度。 但是现在我不知道如何从一些坐标找到所有可能的路线,找到其中最长的路线。我的意思是我不知道什么是最好的方式来回来“叉”,并继续与另一条路线。
我希望解释清楚。提前致谢。
你是说(或没有),你不能从一个较小的移动到一个更大的数字?路线必须走100,100,100,99,99,98,98等等,还是可以走100,79,6,43,87 ......?距离是以平方数量来衡量,还是通过你通过的数字的总和来衡量? –
@ OleV.V。你只能从大到小移动。所以你不能在相同的数字之间移动。 –
所以路线永远不会超过99个步骤。 –