Find number of areas in a matrix

Question

Assume I have a matrix something like this :

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

If two '1' are next to each other (horizontally and vertically only) and therefore belong to the same area. I need to find how many of these areas are there in a matrix. You can see that there's two areas of '1' in this matrix. I've been trying to solve this for hours now but the code gets really big and disgusting. Are there any algorithms out there I could adopt for this problem ?

Answer 1

Here is the Java implementation

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());
    }
}

Here is the test case

@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));

}

Answer 2

I have tried a python implementation that uses DFS algorithmic approach & works with time complexity O(M x N). Input for the function is a M*N list.

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 3

This python function should do the trick (it does on your example and on some others I randomly made up):

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

If you don't really care about:

• Keeping the input matrix intact

• Performance and optimisations

then here's my take on this problem in 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;
}

Once it encounters a 1, it recursively expands over all neighbouring 1 elements, counting them and turning them into 0. If the size of the area is larger than IGN, then it is taken into account.

Notes:

• If you need to keep the original matrix, you would have to use a copy for input.

• If you plan on using this, you should probably turn this code into functions that get the array and its size from their parameters. Global variables and algorithm implementations in main() should be avoided, but I made an exception in this case because it reduces the complexity of the code and allows the algorithm to be more clear.

• With IGN set to 1, lone elements are not considered an area. Changing IGN to 0 will get those too.

• The if (A[j][i] == 1) conditional in the loop is not strictly necessary, but it serves as a minor optimisation by avoiding unnecessary function calls, although compiler optimisations probably make it redudant.

• You can easily modify this to get a listing of the elements in each area.

Answer 5

Would this help? I assume that with "same area" you mean that the points belong to same connected component.

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