java - 二维数组中从最大值到最小值的最长路线

Question

有一个二维数组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 的大小就是这条路线的长度。但是现在我不知道如何从一些坐标中找到所有可能的路线以找到其中最长的路线。我的意思是我不知道返回“岔路口”并继续另一条路线的最佳方式是什么。

我希望解释清楚。提前致谢。

Answer 1

如果您将此问题视为有向图问题，则可以应用已知的图算法。

这是 Johnson's algorithm 的一个实现

首先，它在点矩阵上搜索局部最大值。他们将成为第一批候选人，然后算法对候选人进行迭代，它遵循约翰逊算法。并且它计算到任何点的所有长度。

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 x 10 矩阵)

• 第一个 block :二维矩阵 (10x10)

• 第二 block :从最小值到最大值的最长解的坐标。

• 最后一个 block :坐标的长度。

输出:

 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