查找矩阵中的面积数

Question

假设我有一个类似这样的矩阵：

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

如果两个“1”彼此相邻（仅水平和垂直），因此属于同一区域。我需要找出矩阵中有多少个这些区域。您可以看到该矩阵中有两个区域为“1”。我已经尝试解决这个问题几个小时了，但是代码变得非常大而且令人厌恶。有没有我可以采用的算法来解决这个问题？

Answer 1

如果您并不真正关心：

• 保持输入矩阵完整

• 性能和优化

，那么这是我在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;
}

一旦当它遇到 1 时，它会递归地扩展所有相邻的 1 元素，对它们进行计数并将它们转换为 0。如果该区域的大小大于 IGN，则将其考虑在内。

注意：

• 如果需要保留原始矩阵，则必须使用副本进行输入。

• 如果您打算使用它，您可能应该将此代码转换为从参数获取数组及其大小的函数。应该避免 main() 中的全局变量和算法实现，但我在这种情况下例外，因为它降低了代码的复杂性并使算法更加清晰。

• 将 IGN 设置为 1 时，单独的元素不被视为区域。将 IGN 更改为 0 也会得到这些。

• 循环中的 if (A[j][i] == 1) 条件并不是严格必要的，但它通过避免不必要的函数调用来作为次要优化，尽管编译器可能会进行优化使其冗余。

• 您可以轻松修改它以获取每个区域中的元素列表。

Answer 2

这有帮助吗？我假设“相同区域”意味着这些点属于相同的连接组件。

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

Answer 3

这个 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)

Answer 4

我尝试过使用 DFS 算法方法的 python 实现时间复杂度为 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

Answer 5

这是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));

}