There is 2D array long[50][50] which is filled with random numbers from 0 to 100. I need to find the longest way from the biggest (or first highest) to the smallest. You can move up, down, left and right.
有一个二维数组[50][50]，它包含从0到100的随机数。我需要找到从最大(或最高)到最小的最长的路径。你可以上下左右移动。
I found how to find single way: find the biggest nearest number (but no bigger, that it is) and move there.
我找到了如何找到唯一的方法:找到最近的最大的数字(但不是更大的数字)，然后搬到那里。
public static int measure = 50;
public long[][] map = new long[measure][measure];
My move methods:
我的移动方法:
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];
}
Find nearest biggest:
找到最近的最大:
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);
}
}
Then find the longest way using only nearest biggest values:
然后用最接近的最大值找到最长的方法:
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);
}
}
}
And the size of way would be the length of such route. But now I don't know how to find all possible routes from some coordinates to find the longest of them. I mean I don't know what it is a best way to come back on "fork" and continue with another route.
路的大小就是这条路的长度。但是现在我不知道如何从某个坐标找到所有可能的路径来找到最长的路径。我的意思是我不知道什么是最好的方式回到“叉子”并继续另一条路线。
I hope the explanation is clear. Thanks in advance.
我希望解释清楚。提前谢谢。
1 个解决方案
#1
4
If you see this problem like a directed graph problem, you can apply the known graphs algorithm.
如果您将这个问题视为有向图问题，您可以应用已知的图算法。
This is an implementation of Johnson's algorithm
这是Johnson算法的一个实现
At the first time, It search the local-max values on points matrix. They'll be the first candidates, then the algorithm iterates over candidates, It follows the Johnson's algorithm. And It computes all lengths to any point.
首次在点矩阵上搜索局部最大值。它们将是第一个候选者，然后算法遍历候选者，它遵循Johnson算法。它计算所有长度到任意点。
public class Solver {
private static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
private static class State {
static State best;
State parent;
List<State> children = new ArrayList<>();
int length;
Point p;
public State(State parent, Point p) {
this.parent = parent;
this.p = p;
this.length = parent.length + 1;
this.parent.children.add(this);
if (best.length < length) {
best = this;
}
}
public State(Point p) {
this.parent = null;
this.p = p;
this.length = 1;
if (best == null) {
best = this;
}
}
public void checkParent(State st) {
if (st.length + 1 > length) {
parent.children.remove(this);
this.parent = st;
updateLength();
}
}
private void updateLength() {
this.length = parent.length + 1;
if (best.length < length) {
best = this;
}
for (State state : children) {
state.updateLength();
}
}
}
public static boolean checkRange(int min, int max, int x) {
return min <= x && x < max;
}
public static boolean maxLocal(int x, int y, int[][] points) {
int value = points[x][y];
if (x > 0 && points[x - 1][y] > value) {
return false;
}
if (y > 0 && points[x][y - 1] > value) {
return false;
}
if (x < points.length - 1 && points[x + 1][y] > value) {
return false;
}
return !(y < points[0].length - 1 && points[x][y + 1] > value);
}
private static List<Point> getNeigbours(int x, int y, int[][] points) {
int value = points[x][y];
List<Point> result = new ArrayList<>(4);
if (x > 0 && points[x - 1][y] < value) {
result.add(new Point(x - 1, y));
}
if (y > 0 && points[x][y - 1] < value) {
result.add(new Point(x, y - 1));
}
if (x < points.length - 1 && points[x + 1][y] < value) {
result.add(new Point(x + 1, y));
}
if (y < points[0].length - 1 && points[x][y + 1] < value) {
result.add(new Point(x, y + 1));
}
return result;
}
private static int[][] generateRandomPoint(int width, int height, int max) {
int[][] result = new int[width][height];
Random rand = new Random(0L);
for (int i = 0; i < result.length; i++) {
for (int j = 0; j < result[i].length; j++) {
result[i][j] = rand.nextInt(max);
}
}
return result;
}
public static void main(String[] args) {
int[][] points = generateRandomPoint(50, 50, 100);
State[][] states = new State[points.length][points[0].length];
List<State> candidates = new ArrayList<>(points.length*points[0].length);
for (int x = 0; x < points.length; x++) {
for (int y = 0; y < points[0].length; y++) {
if (maxLocal(x, y, points)) {
states[x][y] = new State(new Point(x, y));
candidates.add(states[x][y]);
}
}
}
while (!candidates.isEmpty()) {
State candidate = candidates.remove(candidates.size() - 1);
for (Point p : getNeigbours(candidate.p.x, candidate.p.y, points)) {
if (states[p.x][p.y] == null) {
states[p.x][p.y] = new State(candidate, p);
candidates.add(states[p.x][p.y]);
} else {
states[p.x][p.y].checkParent(candidate);
}
}
}
State temp = State.best;
List<Point> pointList = new ArrayList<>(temp.length);
while (temp != null) {
pointList.add(temp.p);
temp = temp.parent;
}
for (int x = 0; x < points.length; x++) {
for (int y = 0; y < points[0].length; y++) {
if (points[x][y] < 10) {
System.out.print(" ");
} else if (points[x][y] < 100) {
System.out.print(" ");
}
System.out.print(points[x][y] + " ");
}
System.out.println();
}
System.out.println("-------");
for (Point point : pointList) {
System.out.println(point.x + ", " + point.y + " -> " + points[point.x][point.y]);
}
System.out.println();
System.out.println("lengths:");
for (int x = 0; x < points.length; x++) {
for (int y = 0; y < points[0].length; y++) {
if (states[x][y].length < 10) {
System.out.print(" ");
}
System.out.print(states[x][y].length + " ");
}
System.out.println();
}
}
}
It prints (with 10 x 10 matrix)
打印(10x10矩阵)
-
First block: The 2D-matrix (10x10)
第一块:2d矩阵(10x10)
-
Second block: The coordinates of the longest solution from min to max values.
第二个块:从最小值到最大值的最长解的坐标。
-
Last block: The Coordinate's length.
最后一块:坐标的长度。
output:
输出:
60 48 29 47 15 53 91 61 19 54
77 77 73 62 95 44 84 75 41 20
43 88 24 47 52 60 3 82 92 23
45 45 37 87 2 62 25 53 38 35
60 75 55 30 98 91 74 36 12 62
19 77 16 46 7 16 8 37 43 47
87 88 5 58 8 17 51 18 58 18
38 72 57 51 26 80 97 62 35 20
67 73 17 69 5 52 89 43 1 41
23 80 68 14 16 23 57 22 5 71
-------
5, 4 -> 7
6, 4 -> 8
7, 4 -> 26
7, 3 -> 51
7, 2 -> 57
7, 1 -> 72
8, 1 -> 73
9, 1 -> 80
lengths:
2 3 6 5 6 2 1 4 5 1
1 2 3 4 1 5 2 3 4 5
6 1 7 6 5 4 5 2 1 4
5 4 5 1 6 3 4 3 4 3
4 3 4 5 1 2 3 5 5 1
5 2 5 2 8 4 5 4 3 2
2 1 5 1 7 3 2 4 1 5
4 3 4 5 6 2 1 2 3 4
3 2 5 1 7 3 2 3 4 2
4 1 2 6 5 4 3 4 5 1
#1
4
If you see this problem like a directed graph problem, you can apply the known graphs algorithm.
如果您将这个问题视为有向图问题，您可以应用已知的图算法。
This is an implementation of Johnson's algorithm
这是Johnson算法的一个实现
At the first time, It search the local-max values on points matrix. They'll be the first candidates, then the algorithm iterates over candidates, It follows the Johnson's algorithm. And It computes all lengths to any point.
首次在点矩阵上搜索局部最大值。它们将是第一个候选者，然后算法遍历候选者，它遵循Johnson算法。它计算所有长度到任意点。
public class Solver {
private static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
private static class State {
static State best;
State parent;
List<State> children = new ArrayList<>();
int length;
Point p;
public State(State parent, Point p) {
this.parent = parent;
this.p = p;
this.length = parent.length + 1;
this.parent.children.add(this);
if (best.length < length) {
best = this;
}
}
public State(Point p) {
this.parent = null;
this.p = p;
this.length = 1;
if (best == null) {
best = this;
}
}
public void checkParent(State st) {
if (st.length + 1 > length) {
parent.children.remove(this);
this.parent = st;
updateLength();
}
}
private void updateLength() {
this.length = parent.length + 1;
if (best.length < length) {
best = this;
}
for (State state : children) {
state.updateLength();
}
}
}
public static boolean checkRange(int min, int max, int x) {
return min <= x && x < max;
}
public static boolean maxLocal(int x, int y, int[][] points) {
int value = points[x][y];
if (x > 0 && points[x - 1][y] > value) {
return false;
}
if (y > 0 && points[x][y - 1] > value) {
return false;
}
if (x < points.length - 1 && points[x + 1][y] > value) {
return false;
}
return !(y < points[0].length - 1 && points[x][y + 1] > value);
}
private static List<Point> getNeigbours(int x, int y, int[][] points) {
int value = points[x][y];
List<Point> result = new ArrayList<>(4);
if (x > 0 && points[x - 1][y] < value) {
result.add(new Point(x - 1, y));
}
if (y > 0 && points[x][y - 1] < value) {
result.add(new Point(x, y - 1));
}
if (x < points.length - 1 && points[x + 1][y] < value) {
result.add(new Point(x + 1, y));
}
if (y < points[0].length - 1 && points[x][y + 1] < value) {
result.add(new Point(x, y + 1));
}
return result;
}
private static int[][] generateRandomPoint(int width, int height, int max) {
int[][] result = new int[width][height];
Random rand = new Random(0L);
for (int i = 0; i < result.length; i++) {
for (int j = 0; j < result[i].length; j++) {
result[i][j] = rand.nextInt(max);
}
}
return result;
}
public static void main(String[] args) {
int[][] points = generateRandomPoint(50, 50, 100);
State[][] states = new State[points.length][points[0].length];
List<State> candidates = new ArrayList<>(points.length*points[0].length);
for (int x = 0; x < points.length; x++) {
for (int y = 0; y < points[0].length; y++) {
if (maxLocal(x, y, points)) {
states[x][y] = new State(new Point(x, y));
candidates.add(states[x][y]);
}
}
}
while (!candidates.isEmpty()) {
State candidate = candidates.remove(candidates.size() - 1);
for (Point p : getNeigbours(candidate.p.x, candidate.p.y, points)) {
if (states[p.x][p.y] == null) {
states[p.x][p.y] = new State(candidate, p);
candidates.add(states[p.x][p.y]);
} else {
states[p.x][p.y].checkParent(candidate);
}
}
}
State temp = State.best;
List<Point> pointList = new ArrayList<>(temp.length);
while (temp != null) {
pointList.add(temp.p);
temp = temp.parent;
}
for (int x = 0; x < points.length; x++) {
for (int y = 0; y < points[0].length; y++) {
if (points[x][y] < 10) {
System.out.print(" ");
} else if (points[x][y] < 100) {
System.out.print(" ");
}
System.out.print(points[x][y] + " ");
}
System.out.println();
}
System.out.println("-------");
for (Point point : pointList) {
System.out.println(point.x + ", " + point.y + " -> " + points[point.x][point.y]);
}
System.out.println();
System.out.println("lengths:");
for (int x = 0; x < points.length; x++) {
for (int y = 0; y < points[0].length; y++) {
if (states[x][y].length < 10) {
System.out.print(" ");
}
System.out.print(states[x][y].length + " ");
}
System.out.println();
}
}
}
It prints (with 10 x 10 matrix)
打印(10x10矩阵)
-
First block: The 2D-matrix (10x10)
第一块:2d矩阵(10x10)
-
Second block: The coordinates of the longest solution from min to max values.
第二个块:从最小值到最大值的最长解的坐标。
-
Last block: The Coordinate's length.
最后一块:坐标的长度。
output:
输出:
60 48 29 47 15 53 91 61 19 54
77 77 73 62 95 44 84 75 41 20
43 88 24 47 52 60 3 82 92 23
45 45 37 87 2 62 25 53 38 35
60 75 55 30 98 91 74 36 12 62
19 77 16 46 7 16 8 37 43 47
87 88 5 58 8 17 51 18 58 18
38 72 57 51 26 80 97 62 35 20
67 73 17 69 5 52 89 43 1 41
23 80 68 14 16 23 57 22 5 71
-------
5, 4 -> 7
6, 4 -> 8
7, 4 -> 26
7, 3 -> 51
7, 2 -> 57
7, 1 -> 72
8, 1 -> 73
9, 1 -> 80
lengths:
2 3 6 5 6 2 1 4 5 1
1 2 3 4 1 5 2 3 4 5
6 1 7 6 5 4 5 2 1 4
5 4 5 1 6 3 4 3 4 3
4 3 4 5 1 2 3 5 5 1
5 2 5 2 8 4 5 4 3 2
2 1 5 1 7 3 2 4 1 5
4 3 4 5 6 2 1 2 3 4
3 2 5 1 7 3 2 3 4 2
4 1 2 6 5 4 3 4 5 1