Actualmente estoy enfrentando un problema de algoritmo que no puedo resolver y realmente necesito ayuda con eso.
Aquí está el diseño general:
Así que aquí está el problema al que me enfrento:
Digamos que tengo celdas desbloqueadas (0,0), (1,0), (2,0), (2,1).
En esta situación, no debería ser posible bloquear la celda (2,0), ya que la celda (2,1) perderá cualquier conexión que tenga con (0,0).
¿Cómo puedo implementar tal lógica que haga que las celdas no se puedan volver a bloquear, a menos que sea seguro hacerlo (las siguientes celdas aún tienen conexión con el punto de partida de alguna manera)?
Si esto requiere algún tipo de algoritmo general, no sé cómo buscarlo, así que no dude en proporcionarme su nombre para que pueda aprenderlo. No estudié informática, soy un estudiante autodidacta.
Una forma estándar de hacer esto sería tratar su cuadrícula como un gráfico (un conjunto de vértices y aristas) y verlo como un problema gráfico. Las celdas serían los vértices del gráfico, conectados por los bordes horizontales y verticales entre ellos. Haría un seguimiento de qué celdas/vértices están desbloqueados, con las celdas que bordean las celdas desbloqueadas siendo desbloqueables y todas las demás celdas bloqueadas.
Un "vértice de corte" o "punto de articulación" en un gráfico es un vértice que, si se elimina, desconectaría el gráfico. Desea asegurarse de que una celda no sea un vértice cortado entre las celdas desbloqueadas antes de permitir que se bloquee (ya que hacerlo desconectaría una parte de las celdas desbloqueadas). Puede realizar una búsqueda en profundidad primero solo sobre las celdas desbloqueadas para encontrar sus puntos de articulación y comprobar que la celda que se va a bloquear no es uno de esos puntos antes de bloquearla.