Find the number of areas in the matrix

Question

Suppose I have a matrix like this:

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

If two "1s" are located next to each other (only horizontally and vertically) and therefore belong to the same area. I need to find how many of these areas are in the matrix. You can see that there are two “1” areas in this matrix. I tried to solve this for hours, but the code is getting really big and disgusting. Are there any algorithms I could take for this problem?

Answer 1

If you don't care:

• Keeping the original matrix intact

• Performance and Optimization

then here I will take 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; } 

As soon as it encounters 1 , it recursively expands across all neighboring elements of 1 , counting them and turning them into 0 . If the size of the region is larger than the IGN , then it is taken into account.

Notes:

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

• If you plan to use this, you should probably include this code in functions that receive the array and its size in terms of its parameters. Global variables and the implementation of algorithms 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 understandable.

• If IGN set to 1 , single elements are not considered an area. Changing IGN to 0 will also get them.

• The if (A[j][i] == 1) condition if (A[j][i] == 1) in the loop is not strictly necessary, but it serves as a minor optimization, avoiding unnecessary function calls, although optimizing the compiler probably makes it realistic.

• You can easily change this to get a list of items in each area.

Answer 2

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

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

Answer 3

This python function should do the trick (this is done on your example and on some others that I accidentally did):

 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((ii,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

I tried a python implementation that uses the DFS algorithmic approach and works with O (M x N) time complexity. The input for the function is the list 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

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