有一个二维数组long[50][50]，它由0到100的随机数填充。我需要找到从最大值(或第一个最大值)到最小值的最长路径。你可以上下左右移动
我发现了如何找到唯一的方法:找到最大的最近的数字(但不是更大的，它是)，并移动到那里。
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];
}
查找最近的最大值:
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的大小为该路线的长度。但是现在我不知道如何从一些坐标中找到所有可能的路线来找到其中最长的。我的意思是，我不知道回到"岔路口"并继续走另一条路线的最佳方式是什么。
我希望解释清楚。
如果你认为这个问题是一个有向图问题，你可以应用已知的图算法。
这是Johnson算法的一个实现
第一次搜索点矩阵的local-max值。他们将是第一批候选者，然后算法对候选者进行迭代，它遵循约翰逊算法。它计算到任意点的所有长度
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();
}
}
}
打印(10 × 10矩阵)
第一块:2D-matrix (10x10)
第二个块:从min到max值的最长解的坐标
最后一个块:坐标的长度
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