найти соседей в 2d массиве по положению элементов

Question

Мне нужно найти соседей в 2d массиве по позиции элементов

Доступные данные:

Размер сетки . например - 3 * 3 вернет 3, 4 * 4 вернет 4

количество заполненных ячеек в сетке . например - 4

получить координату х заполненной ячейки - например, 0 или 1 или 2 и т. д. c

получить координату у заполненной ячейки ячейка - например, 0 или 1 или 2 и т.д. c

например,

int[][] room = {
            {0, 0, X},
            {0, X, 0},
            {X, 0, 0}
    };

Здесь, размер сетки = 3

количество заполненных ячеек в сетка = 3 (так как есть три «X», не имеет значения, какое значение оно имеет в других ячейках)

получить координату х заполненной ячейки - для 1-го элемента это 0, для 2-го элемента это 1, для 3-го элемента это 2

получить координату y заполненной ячейки - для 1-го элемента это 2, для 2-го элемента это 1, для 3-го элемента это 0

Итак, координаты становятся (0,2), (1,1), (2,0)

Мне нужно найти число «X» хотя бы с одним соседним «X» , «Х» считаются соседями, если они расположены рядом друг с другом в основных направлениях, но не по диагонали. Таким образом, вышеприведенный случай вернул бы 0.

int[][] room = {
            {X, X, 0},
            {0, 0, 0},
            {0, 0, 0}
    };

это должно вернуть 2.

Я использую язык Java.

Я пытался перебирать количество заполненных элементы и используйте соседнюю логику c, как показано ниже, но она ломается для некоторых или других случаев. Сосед над вами = (x, y-1),

Сосед под вами = (x, y + 1),

Сосед слева от вас = (x-1, y),

Сосед справа от вас = (x + 1, y)

for (int x = 0; x < nums; x++) {
        int xcord = xmap.get(x); //return x cord
        int ycord = ymap.get(x); //return y cord
        int xcordLeft = x - 1 >= 0 ? xmap.get(x - 1) : 0;
        int ycordLeft = x - 1 >= 0 ? ymap.get(x - 1) : 0;

        int xcordRight = x + 1 < size ? xmap.getOrDefault(x + 1, 0) : 0;
        int ycordRight = x + 1 < size ? ymap.getOrDefault(x + 1, 0) : 0;

        int xcordTop = xcord - 1 >= 0 ? xmap.get(xcord - 1) : 0;
        int ycordTop = ymap.get(ycord);

        int ycordBottom = ymap.get(ycord);*/
        //left
        if (xcord >= 0 && x - 1 >= 0 && xcord == xcordLeft && ycord - 1 == ycordLeft) {
            neighbours++;
        }
        //right
        if (xcord >= 0 && x + 1 < size && xcord == xcordRight && ycord + 1 == ycordRight) {
            neighbours++;
        }
        //top
        if (xcord >= 0 && xcord - 1 >= 0 && xcord - 1 == xcordTop && ycord == ycordTop) {
            neighbours++;
        }

        //bottom
    }

Answer 1

Вы работаете из списка координат, которые указывают, где находятся X.

Две ячейки p ( x _p , y _p ) q ( x _q , y _q ) рядом, когда расстояние до Манхэттена равно единице:

| x _p - x _q | + | y _p - y _q | = 1

Вместо того, чтобы пытаться найти координаты верхнего, нижнего, левого и правого соседей и найти их в вашем списке, выполните итерацию по списку и сосчитайте соседей:

for (int i = 0; i < nums; i++) {
    int x = xmap.get(i);
    int y = ymap.get(i);
    int neighbors = 0;

    for (int j = 0; j < nums; j++) {
        int xx = xmap.get(j);
        int yy = ymap.get(j);

        if ((abs(x - xx) + abs(y - yy) == 1) {
            neighbors++;
        }
    }

    if (neighbors) // do stuff
}

Манхэттенское расстояние ячейки до самого себя равно 0, поэтому она не считается соседом. Этот код не очень эффективен для больших плотных сеток, но если у вас мало X, вложенные петли должны быть в порядке.

Answer 2

Сделать это простым и понятным.
Подсчитать соседей, проверив все четыре смежные координаты, и иметь некоторое условие, которое проверяет, находится ли соседняя координата в границах:

bool inBounds(int x, int y){
    return 0 <= x and x < size and 0 <= y and y < size;
}

int countNeighbours(int x, int y) {
    int count = 0;
    for(int i=-1; i<=1; i+=2){
        if(inBounds(x+i, y))
            if(data[x+i][y] == X){
                count++;
            }
        }
        if(inBounds(x, y+i))
            if(data[x][y+i] == X){
                count++;
            }
        }
    }
    return count;
}

int countGroupedEntries(){
    int count = 0;
    for(int x=0; x<size; x++){
        for(int y=0; y<size; y++){
            if(data[x][y] == X){
                if(countNeighbours(x,y) != 0){
                    count++;
                }
            }
        }
    }
    return count;
}

Я имею в виду некоторый алгоритм здесь может быть разумнее, но если у вас нет какой-либо точки эффективности, сделайте алгоритм как можно более простым, сделайте его читабельным (не то, чтобы этот алгоритм был особенно плохим, работает в Θ (размер²) просто отлично, только Рассмотрим линейный коэффициент).
Выполнение проверки inBounds вместо того, чтобы быть уверенным, что вы не выходите за пределы в особых случаях, удерживает метод countNeighbours от переполненности.

Answer 3

Я предполагаю, что вы сохраняете координаты всех x в двух последовательных картах (одна для x и одна для y). так, например,

    {X , X , 0 , X},
    {X , 0 , X , X}
    {0 , 0 , X , X}
    {X , X,  0 , 0}

поэтому ваша карта будет иметь такую ​​запись

    xmap = {
            0 : 0,
            1 : 1,
            2 : 3,
            3 : 0,
            4 : 2,
            5 : 3,
            6 : 2,
            7 : 3,
            8 : 0,
            9 : 1
        }
    ymap = {
            0 : 0,
            1 : 0,
            2 : 0,
            3 : 1,
            4 : 1,
            5 : 1,
            6 : 2,
            7 : 2,
            8 : 3,
            9 : 3,
        }

Я думаю, что левые и правые можно редактировать следующим образом

      //left
        if (xcord >= 0 && x - 1 >= 0 && xcord - 1 == xcordLeft && ycord == ycordLeft) {
            neighbours++; //comparing (x - 1 , y) && (x , y)
        }
      //right
        if (xcord >= 0 && x + 1 < size && xcord + 1 == xcordRight && ycord == ycordRight) {
            neighbours++; // comparing(x , y) && (x + 1 , y)
        }

на самом деле xcordTop должно быть ycordTop, но давайте предположим, что это эквивалентно нахождению верхнего элемента

the mistake you are doing is that how can you be sure that
int xcordTop = xcord - 1 >= 0 ? xmap.get(xcord - 1) : 0; will give you coordinate of just upper element, because key of
the map is not x coordinates it is just numbering of X'S

, поэтому для 7-го X (индекс которого равен нулю в нумерации на основе 0) в данной матрице, давайте возьмем его координаты x и y

xcord = 2 
ycord = 2
now let's us take xmap.get(2)
what do we get xcordTop = 0

, даже если мы go из ycordTop logi c, это снова даст нам неправильную координату, поскольку значения ключа карты являются просто значением последовательности всего X

so let's take ymap.get(ycord) 
ycord = 2
so ycordTop = ymap.get(2) 
we get ycordTop = 0 so which is 0th row

таким образом, простое решение состоит в том, чтобы просто пройти 2d массив и проверить всех соседей, как вы упомянули, которые будут

for(int y = 0; y < array.length; ++y){
    for(int x = 0; x < array[y].length; ++x){
        if(array[x][y] == 'X'){
            if(x - 1 >= 0 && array[x - 1][y] == 'X'){
                ++neighbors;
            }
            else if(x + 1 < array[y].length && array[x + 1][y] == 'X'){
                ++neighbors;
            }
            else if(y - 1 >= 0  && array[x][y - 1] == 'X'){
                ++neighbors;
            }
            else if(y + 1 < array.length && array[x][y + 1] == 'X'){
                ++neighbors;
            }
        }
    }
}

Answer 4

Если вы хотите посчитать количество отношений соседства, вы можете:

private int countNeighborRelations(int[][] array, int yourX) {
    int neighborRelationCount = 0;
    for (int y = 0; y < array.length; y++) {
        for (int x = 0; x < array[y].length - 1; x++) {
            if (array[y][x] == yourX && array[y][x + 1] == yourX) {
                neighborRelationCount += 2;
            }
        }
    }
    for (int y = 0; y < array.length - 1; y++) {
        for (int x = 0; x < array[y].length; x++) {
            if (array[y][x] == yourX && array[y + 1][x] == yourX) {
                neighborRelationCount += 2;
            }
        }
    }
    return neighborRelationCount;
}

Если вы хотите посчитать, сколько из ваших X имеет neigbourHoodRelations (другими словами, все X имеют хотя бы одного соседа) Вы можете использовать следующий код:

private int countNeighbors(int[][] array, int yourX) {
    int[][] neighborRelationCount = new int[array.length][array[0].length];
    for (int y = 0; y < array.length; y++) {
        for (int x = 0; x < array[y].length - 1; x++) {
            if (array[y][x] == yourX && array[y][x + 1] == yourX) {
                neighborRelationCount[y][x]++;
                neighborRelationCount[y][x + 1]++;
            }
        }
    }
    for (int y = 0; y < array.length - 1; y++) {
        for (int x = 0; x < array[y].length; x++) {
            if (array[y][x] == yourX && array[y + 1][x] == yourX) {
                neighborRelationCount[y][x]++;
                neighborRelationCount[y + 1][x]++;
            }
        }
    }
    int neighbourCount=0;
    for (int y = 0; y < neighborRelationCount.length; y++) {
        for (int x = 0; x < neighborRelationCount[y].length; x++) {
            if (0<neighborRelationCount[y][x]) {
                neighbourCount++;
            }
        }
    }
    return neighbourCount;
}

Конечно, есть более простые решения, если вы используете другой формат данных, но с примитивом int [] [] я думаю, это самый простой способ.

Вот как я тестировал функциональность:

    @Test
    public void testRelations() {
        // TODO Auto-generated method stub
        int[][] room0_0 = { { 1, 0, 1 }, { 0, 1, 0 }, { 1, 0, 1 } };
        int[][] room2_2 = { { 1, 1, 0 }, { 0, 0, 0 }, { 0, 0, 0 } };
        int[][] room4_3 = { { 1, 1, 0 }, { 0, 1, 0 }, { 0, 0, 0 } };
        int[][] room4_4 = { { 1, 1, 0 }, { 0, 0, 0 }, { 0, 1, 1 } };
        int[][] room8_5 = { { 1, 1, 0 }, { 0, 1, 0 }, { 0, 1, 1 } };
        int[][] room24_9 = { { 1, 1, 1 }, { 1, 1, 1 }, { 1, 1, 1 } };
        assertTrue(countNeighborRelations(room0_0, 1)==0);
        assertTrue(countNeighborRelations(room2_2, 1)==2);
        assertTrue(countNeighborRelations(room4_3, 1)==4);
        assertTrue(countNeighborRelations(room4_4, 1)==4);
        assertTrue(countNeighborRelations(room8_5, 1)==8);
        assertTrue(countNeighborRelations(room24_9, 1)==24);
        assertTrue(countNeighbors(room0_0, 1)==0);
        assertTrue(countNeighbors(room2_2, 1)==2);
        assertTrue(countNeighbors(room4_3, 1)==3);
        assertTrue(countNeighbors(room4_4, 1)==4);
        assertTrue(countNeighbors(room8_5, 1)==5);
        assertTrue(countNeighbors(room24_9, 1)==9);
    }

EDIT добавил полные реализации для полной запрашиваемой функциональности

Следующий код имеет сложность O (gridSize) ^ 2)

private int neigbours(Collection<CoordinatedObject> cos,int gridSize) {
    boolean[][] array=new boolean[gridSize][gridSize];
    for(CoordinatedObject co:cos) {
        array[co.getX()][co.getY()]&=true;
    }
    boolean[][] neighborRelations = new boolean[array.length][array[0].length];
    for (int y = 0; y < array.length; y++) {
        for (int x = 0; x < array[y].length - 1; x++) {
            if (array[y][x] && array[y][x + 1]) {
                neighborRelations[y][x]&=true;
                neighborRelations[y][x + 1]&=true;
            }
        }
    }
    for (int y = 0; y < array.length - 1; y++) {
        for (int x = 0; x < array[y].length; x++) {
            if (array[y][x] && array[y + 1][x]) {
                neighborRelations[y][x]&=true;
                neighborRelations[y + 1][x]&=true;
            }
        }
    }
    int neighbourCount=0;
    for (int y = 0; y < neighborRelations.length; y++) {
        for (int x = 0; x < neighborRelations[y].length; x++) {
            if (neighborRelations[y][x]) {
                neighbourCount++;
            }
        }
    }
    return neighbourCount;
}