número Búsqueda de zonas en una matriz

Question

Supongamos que tengo una matriz algo como esto:

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

Si dos '1' están uno junto al otro (horizontal y vertical solamente) y, por tanto, pertenecen a la misma zona. Necesito encontrar cuántas de estas áreas hay en una matriz. Puedes ver que hay dos áreas de '1' en esta matriz. He estado tratando de resolver esto durante horas pero el código se vuelve realmente grande y desagradable. ¿Hay algún algoritmo que pueda adoptar para este problema?

Answer 1

Si usted realmente no se preocupan por:

• Mantener la matriz de entrada intacta

• Rendimiento y optimizaciones

entonces aquí es mi opinión sobre este problema en 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; 
} 

Una vez que se encuentra un 1, se expande de forma recursiva sobre todos los elementos de 1 vecinos, contando ellos y convertirlos en 0. Si el tamaño del área es mayor que IGN, entonces se tiene en cuenta.

Notas:

• Si usted necesita para mantener la matriz original, que tendría que utilizar una copia para la entrada.

• Si planea usar esto, probablemente deba convertir este código en funciones que obtengan la matriz y su tamaño de sus parámetros. Deben evitarse las variables globales y las implementaciones de algoritmo en main(), pero hice una excepción en este caso porque reduce la complejidad del código y permite que el algoritmo sea más claro.

• Con IGN establecido en 1, los elementos únicos no se consideran áreas. Cambiando IGN a 0 obtendrá esos también.

• El condicional if (A[j][i] == 1) en el ciclo no es estrictamente necesario, pero sirve como una optimización menor al evitar llamadas a funciones innecesarias, aunque las optimizaciones del compilador probablemente lo conviertan en redudant.

• Puede modificar esto fácilmente para obtener una lista de los elementos en cada área.

Answer 2

¿Esto ayudaría? Supongo que con "misma área" quiere decir que los puntos pertenecen al mismo componente conectado .

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

Answer 3

Esta función pitón debe hacer el truco (lo hace en el ejemplo y en algunos otros que hizo al azar hacia arriba):

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

He tratado de una implementación de Python que utiliza DFS enfoque algorítmico & obras con la complejidad del tiempo O (M x N). La entrada para la función es una lista 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

Aquí está la implementación de 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()); 
    } 
} 

Aquí es el caso de prueba

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

}