Encontrar secciones inalcanzables de un mapa en 2D

Question

No quiero que me resuelvas este problema, solo quiero pedirte algunas ideas.

Esta es la entrada siguiente, y representa un mapa. La 'x' representa tierra, y los puntos - agua. Entonces, con la 'x' puede representar 'islas' en el mapa.

xxx.x...xxxxx   
xxxx....x...x   
........x.x.x   
..xxxxx.x...x  
..x...x.xxx.x   
..x.x.x...x..   
..x...x...xxx   
...xxxxxx....   
x............ 

Como se puede ver, hay algunas islas que están cerrados, es decir, si un barco está dentro de su territorio, que no será capaz de salir, por ejemplo:

..xxxxx.  
..x...x.   
..x.x.x.   
..x...x. 
..xxxxx. 

Y hay algunas islas abierta que es posible salir de ellos, ex:

.xxxxx   
.x...x   
.x.x.x   
.xxx.x  

El problema es el siguiente: para un mapa N x M dada como los anteriores, calcule howm cualquiera de las islas están abiertas, y cuántos son cerrado.

Repito: no quiero que lo resuelvas, solo necesito algunas sugestiones, ideas para resolver. gracias

Answer 1

Creo que usar el buen algoritmo de llenado de inundación viejo debería decirle si desde algún punto puede llegar a otro punto.

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

Además, es posible que necesite para definir mejor lo que entendemos por el interior y el exterior (creo).

Answer 2

Simplemente haga un gráfico conectado desde todos los puntos (márquelos mientras se conecta) y cuando termine - verifique si alguno de los nodos del gráfico está en el perímetro. luego pasa al siguiente punto sin marcar.

Hay algunos algoritmos conocidos comunes para crear un gráfico conectado ....

Answer 3

Se puede leer en una matriz, y luego buscar. o x, y cuando encuentre a. o x, ejecuta una función recursiva que busca conexiones adyacentes. Cuando termines, busca el siguiente. o x que aún no ha sido analizado y repita.

Answer 4

Supongo que al cerrar se refiere a una isla que contiene al menos un cuadrado de mar, desde el cual no se puede llegar a las fronteras del mapa; y por abierto te refieres a cualquier otra isla.

Por lo tanto, primero descubra qué azulejos de mar son accesibles desde los bordes del mapa - mediante el relleno de inundación de cualquier azulejo de mar en el borde y marcando los que pase. Si quedan tejas de mar en el borde, continúe llenando la inundación desde allí.

Ahora que ha marcado todos los mosaicos accesibles desde el borde, todas las demás losetas de mar están encerradas por tierra. Puede encontrar, para cada una de ellas, la isla que lo encierra (por ejemplo, yendo hacia el norte hasta detectar tierra), y usar relleno de inundación en las casillas de tierra, para marcar las casillas de tierra que pertenecen a la isla.

De esta manera puede contar islas que encierran azulejos de mar - islas "cerradas".

Todos los mosaicos que quedan sin marcar pertenecen a una isla "abierta". use relleno de inundación nuevamente para contar esos.

Answer 5

Estas son algunas normas de etiquetado simples:

• agua es ya sea abierto o cerrado
• Edge es mar abierto
siguiente para abrir el agua está abierto algoritmo de inundaciones
• agua

Answer 6

, o BFS