Найти количество областей в матрице

matrix

2272 просмотра

5 ответа

1136 Репутация автора

Предположим, у меня есть матрица что-то вроде этого:

1 1 1 0 0 0
1 1 1 0 0 1
0 0 0 0 0 1

Если два «1» находятся рядом друг с другом (только по горизонтали и вертикали) и, следовательно, принадлежат к одной и той же области. Мне нужно найти, сколько из этих областей есть в матрице. Вы можете видеть, что в этой матрице есть две области «1». Я пытаюсь решить эту проблему часами, но код становится действительно большим и отвратительным. Есть ли какие-либо алгоритмы, которые я мог бы принять для этой проблемы?

Автор: Marijus Источник Размещён: 09.02.2011 03:33

Ответы (5)


0 плюса

97941 Репутация автора

Это поможет? Я полагаю , что с « той же самой области» вы имеете в виду , что точки принадлежат одной компоненте связности .

http://en.wikipedia.org/wiki/Connected_Component_Labeling

Автор: ypercubeᵀᴹ Размещён: 09.02.2011 03:41

7 плюса

67884 Репутация автора

Решение

Если вас не волнует:

  • Сохранение входной матрицы без изменений

  • Производительность и оптимизация

тогда вот мой взгляд на эту проблему в C:

#include <stdio.h>

#define X       8
#define Y       4

#define IGN     1

int A[Y][X] = {
        { 1, 1, 1, 0, 0, 0, 0, 1 },
        { 1, 1, 1, 0, 0, 1, 0, 1 },
        { 0, 0, 0, 0, 0, 1, 0, 1 },
        { 0, 0, 0, 0, 0, 1, 1, 1 },
};

int blank(int x, int y) {
        if ((x < 0) || (x >= X) || (y < 0) || (y >= Y) || (A[y][x] == 0))
                return 0;

        A[y][x] = 0;

        return 1 + blank(x - 1, y) + blank(x + 1, y) + blank(x, y - 1) + blank(x, y + 1);
}

int main() {
        int areas = 0;

        int i, j = 0;

        for (i = 0; i < X; ++i)
                for (j = 0; j < Y; ++j)
                        if (A[j][i] == 1)
                                if (blank(i, j) > IGN)
                                        areas++;

        printf("Areas: %i\n", areas);

        return 0;
}

Как только он встречает a 1, он рекурсивно расширяется по всем соседним 1элементам, считая их и превращая в них 0. Если размер области больше чем IGN, то это учитывается.

Примечания:

  • Если вам нужно сохранить исходную матрицу, вам придется использовать копию для ввода.

  • Если вы планируете использовать это, вам, вероятно, следует превратить этот код в функции, которые получают массив и его размер из своих параметров. main()Следует избегать глобальных переменных и реализаций алгоритма , но я сделал исключение в этом случае, поскольку это уменьшает сложность кода и позволяет алгоритму быть более понятным.

  • Если IGNустановлено значение 1, одиночные элементы не считаются областью. Переходя IGNна 0это тоже получишь.

  • if (A[j][i] == 1)Условный цикл не является строго необходимым, но он служит оптимизации незначительной, избегая ненужных вызовов функций, хотя компилятор оптимизаций , вероятно , сделать это redudant.

  • Вы можете легко изменить это, чтобы получить список элементов в каждой области.

Автор: thkala Размещён: 25.02.2011 01:56

0 плюса

141 Репутация автора

Эта функция Python должна сделать свое дело (она работает на вашем примере и на некоторых других, которые я сделал случайным образом):

def countareas(A):

    areas=0

    maxi=len(A)
    if maxi==0:
        return(0)

    maxj=len(A[0])
    if maxj==0:
        return(0)

    allposlist=[]

    a=0
    while a<maxi:
        b=0
        while b<maxj:
            if (a,b) not in allposlist and A[a][b]!=0:
                areas+=1        
                allposlist.append((a,b))
                thisarea=[(a,b)]
                cont=True
                while cont:
                    pair = thisarea.pop(0)
                    i=pair[0]
                    j=pair[1]
                    if i-1>=0:
                        if (i-1,j) not in allposlist and A[i-1][j]==A[i][j]:
                            thisarea.append((i-i,j))
                            allposlist.append((i-1,j))
                    if i+1<maxi:
                        if (i+1,j) not in allposlist and A[i+1][j]==A[i][j]:
                            thisarea.append((i+1,j))
                            allposlist.append((i+1,j))
                    if j-1>=0:
                        if (i,j-1) not in allposlist and A[i][j-1]==A[i][j]:
                            thisarea.append((i,j-1))
                            allposlist.append((i,j-1))
                    if j+1<maxj:
                        if (i,j+1) not in allposlist and A[i][j+1]==A[i][j]:
                            thisarea.append((i,j+1))
                            allposlist.append((i,j+1))

                    if len(thisarea)==0:
                        cont=False
            b+=1
        a+=1

    return(areas)
Автор: Nick Размещён: 31.08.2015 10:55

0 плюса

117 Репутация автора

Я пробовал реализацию на Python, которая использует алгоритмический подход DFS и работает с временной сложностью O (M x N). Входом для функции является список M * N.

rows, cols = 0, 0

# The main function that provides count of islands in a given M*N matrix
def traverse_dfs(A, directions, i, j, visited):
    global rows, cols

    # A function to check if a given cell (row, col) can be included in DFS
    def isSafe(A, row, col, visited, current):
        return ( row >=0 and row < rows and col >=0 and col < cols and \
            not visited[row][col] and (current == A[row][col]))
    visited[i][j] = True

    # print i, j
    # Recurrence for all connected neighbours
    for k in range(len(directions)):
        if isSafe(A, i+directions[k][0], j+directions[k][1], visited, A[i][j]):
            traverse_dfs(A, directions, i+directions[k][0], j+directions[k][1], visited)

def countRegions(A):
    global rows, cols
    rows, cols = len(A), len(A[0])
    print A
    if(rows is 1 and cols is 1):
        return 1

    # Below list gives the possible directions in which we can move
    directions = [[1, 0], [0, -1], [-1, 0], [0, 1]]
    visited = []

    # Make a bool array to mark visited cells, Initially all cells are unvisited
    for i in range(rows):
        l = []
        for j in range(cols):
            l.append(False)
        visited.append(l)

    count = 0
    for i in range(rows):
        for j in range(cols):
            if not visited[i][j]:
                traverse_dfs(A, directions, i, j, visited)
                count += 1
    print "Regions count: {0}".format(count)


[[5, 4, 4], [4, 3, 4], [3, 2, 4], [2, 2, 2], [3, 3, 4], [1, 4, 4], [4, 1, 1]]
Regions count: 11
[[2, 3, 3], [4, 4, 1], [2, 1, 1], [5, 2, 3], [5, 2, 2], [1, 4, 1], [3, 4, 1]]
Regions count: 12
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Regions count: 9
[[1, 1, 1], [2, 2, 2], [3, 3, 3]]
Regions count: 3
[[1, 1], [2, 2], [3, 3]]
Regions count: 3
[[1, 2], [1, 2]]
Regions count: 2
[[1, 2], [3, 4]]
Regions count: 4
[[1, 1], [1, 1]]
Regions count: 1
[[1], [2]]
Regions count: 2
[[1, 0, 1], [0, 1, 0], [1, 0, 1]]
Regions count: 9
Автор: cpp-coder Размещён: 09.11.2015 05:13

0 плюса

602 Репутация автора

Вот реализация Java

public static int numberOfIslands(int[][] m) {
    int rows = m.length;
    int columns = m[0].length;
    boolean[][] visited = new boolean[rows][columns];
    int count = 0;

    for (int row = 0; row < rows; row++) {
        for (int column = 0; column < columns; column++) {
            if (m[row][column] == 1 && !visited[row][column]) {
                dfs(m, row, column, visited);
                count++;
            }               
        }
    }

    return count;
}

private static void dfs(int[][] m, int row, int column, boolean[][] visited) {
    visited[row][column] = true;
    for (Direction direction : Direction.values()) {
        int newRow = row + direction.getRowDelta();
        int newColumn = column + direction.getColumnDelta();
        if (isValid(m, newRow, newColumn, visited)) {
            dfs(m, newRow, newColumn, visited);
        }
    }
}

private static boolean isValid(int[][] m, int row, int column, boolean[][] visited) {
    if (row >= 0 && row < m.length &&
            column >=0 && column < m[0].length &&
            m[row][column] == 1 &&
            !visited[row][column]) {
        return true;
    }
    return false;
}

private enum Direction {
    N(-1, 0),NE(-1, 1), E(0, 1),  SE(1,1), S(1, 0), SW(1, -1), W(0, -1), NW(-1, -1);

    private int rowDelta;
    private int columnDelta;

    private Direction(int rowDelta, int columnDelta) {
        this.rowDelta = rowDelta;
        this.columnDelta = columnDelta;
    }

    public int getRowDelta() {
        return rowDelta;
    }

    public int getColumnDelta() {
        return columnDelta;
    }

    @Override
    public String toString() {
        return String.format("%s(%d, %d)", this.name(), this.getRowDelta(), this.getColumnDelta());
    }
}

Вот тестовый пример

@Test
public void countIslandsTest() {
    int[][] m = { { 1, 1, 0, 0 },
                  { 0, 0, 0, 1 },
                  { 0, 0, 1, 1 }
                };
    int result = MatrixUtil.numberOfIslands(m);
    assertThat(result, equalTo(2));

    m = new int[][]{ {1, 1, 0, 0, 0},
              {0, 1, 0, 0, 1},
              {0, 0, 0, 1, 1},
              {0, 0, 0, 0, 0},
              {0, 0, 0, 0, 1}
            };
    result = MatrixUtil.numberOfIslands(m);
    assertThat(result, equalTo(3));

}
Автор: craftsmannadeem Размещён: 08.03.2016 04:02
Вопросы из категории :
32x32