Нахождение координат в многомерном массиве

Question

У меня есть массив int[][], например, так:

int[][] arr = { {3, 4, 3, 5, -9}, 
                {0, 4, 4, -8, 6}, 
                {1, 1, 3, -9, 6}, 
                {4, 3, -2, 5, 6}};

Фактическая проблема состоит в том, чтобы найти прямоугольник в массиве 2-й, чтобы каждый угол прямоугольника имел те же значения, что и уголэлементы в 2-м массиве.Например, углы 3, -9, 4 и 6. И получающийся прямоугольник - тот в [0, 2], [0, 4], [1, 2], [1, 4].

Моя попытка сначала найти позиции всех [3, -9] в каждом ряду, поэтому, например, в первом ряду есть два из них в [{0,0}, {0,4}] и [{0,2}, {0,4}].

Я могу сделать стандартные вложенные циклы for, чтобы найти каждые 3 и каждые 9:

for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr[i].length; j++) {
    // if value is 3, store the co-ordinates
    // if value is 9, store the co-ordinates (separately)
    }
}

Но затем я вынужден пройтись по 2 спискам (из 3-х и -9-х) и проверить, что для каждых 3-х есть тот же -9 в той же строке, и что он находится после него в этой строке, и если да,объединить и сохранить эти две координаты вместе.

Тогда, конечно, я должен сделать то же самое с 4 и 6, и это быстро превратилось в большой беспорядок.

Возможно, яЯ смотрю на все это неправильно, и может быть рассмотрено XY Проблема .

Мой вопрос: как мне найти прямоугольник в 2d-массиве с углами указанного прямоугольника, совпадающего свнешние углы 2-го массива?

Answer 1

А как насчет простого поиска?

public static List<Point> findRectangle(int[][] arr) {
    int height = arr.length;
    int width = arr[0].length;

    for (int rowTop = 0; rowTop < height - 1; rowTop++) {
        for (int colLeft = rowTop == 0 ? 1 : 0; colLeft < width - 1; colLeft++) {
            // find new left-top corner
            if (arr[rowTop][colLeft] != arr[0][0])
                continue;

            int colRight = colLeft + 1;

            while (colRight < width && arr[rowTop][colRight] != arr[0][width - 1]) {
                colRight++;
            }

            if (colRight == width)
                continue;

            // find new left-bottom corner
            int rowBottom = rowTop + 1;

            while (rowBottom < height && arr[rowBottom][colLeft] != arr[height - 1][0]) {
                rowBottom++;
            }

            if (rowBottom == height || arr[rowBottom][colRight] != arr[height - 1][width - 1])
                continue;

            return Arrays.asList(
                    new Point(rowTop, colLeft),
                    new Point(rowTop, colRight),
                    new Point(rowBottom, colLeft),
                    new Point(rowBottom, colRight));
        }
    }

    return Collections.emptyList();
}

public static final class Point {

    private final int row;
    private final int col;

    public Point(int row, int col) {
        this.row = row;
        this.col = col;
    }
}