Самый длинный маршрут в 2D массиве от макс до мин
Есть 2D массив 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 будет длина такого маршрута. Но сейчас я не знаю, как найти все возможные маршруты по некоторым координатам, чтобы найти самый длинный из них. Я имею в виду, что не знаю, как лучше вернуться на "развилку" и продолжить другой маршрут.
Я надеюсь, что объяснение понятно. Заранее спасибо.
1 ответ
Решение
Если вы видите эту проблему как задачу ориентированного графа, вы можете применить алгоритм известных графов.
Это реализация алгоритма Джонсона
В первый раз, поиск локальных максимальных значений по матрице точек. Они будут первыми кандидатами, затем алгоритм перебирает кандидатов. Он следует алгоритму Джонсона. И он вычисляет все длины в любой точке.
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-матрица (10х10)
Второй блок: координаты самого длинного решения от минимальных до максимальных значений.
Последний блок: длина координаты.
выход:
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