¿Cómo detectar cuadrados en una cuadrícula que NUNCA puede ser parte de una ruta más corta después de agregar bloques?

Question

Tengo una grilla con inicio, final y algunas paredes. Las unidades toman la ruta más corta (moviéndose solo hacia arriba/abajo/izquierda/derecha) desde el principio hasta el final, sin pasar por las paredes.

El usuario se le permite añadir tantas paredes adicionales, ya que quiere cambiar la ruta.

Sin embargo, observe que se añaden, no importa cuántas paredes o dónde se añaden, hay algunas plazas que puede Nunca ser la parte del camino más corto!

Estas plazas no pueden ser parte de la ruta más corta!

Estoy buscando una manera de detectar qué cuadrados nunca pueden ser parte de la ruta más corta.

---

Los casos anteriores son fáciles de encontrar; pero hay casos más complejos. Considere:

En la imagen anterior, ninguno de los cuadros con puntos rojos nunca puede ser parte de la mejor ruta, porque sólo hay una entrada a esa zona, y es sólo dos espacios de ancho. Si tuviera tres espacios de ancho, o si se eliminara alguna de las paredes, la mayoría de esos cuadrados podrían ser parte del mejor camino.

He estado tratando de encontrar una manera de detectar casos como el anterior (principalmente usando min-cuts y rellenos de inundación), pero sin éxito. ¿Alguien sabe de una manera de resolver este problema?

Answer 1

Considere cualquier ruta de S a F. Esa ruta podría ser una ruta más corta (si elimina todos los demás cuadrados) a menos que pueda tomar "accesos directos" usando solo esos mosaicos. Esto solo ocurre cuando tienes dos cuadrados adyacentes que no están adyacentes en la ruta. Entonces, debes considerar todos los pares de cuadrados adyacentes; cualquier cosa que desconecten de S o F (sin desconectar S de F) no puede formar parte del camino más corto. Además, las fichas que se pueden desconectar por un solo cuadrado no pueden formar parte de ninguna ruta (que no repita los vértices) de S a F, por lo que también deben ir.

Deje N ser el número de cuadrados en la cuadrícula. Para cualquier par particular de cuadrados (hay O (N) de ellos), lo que se desconecta se puede calcular en O (N) tiempo con un relleno, entonces esto es O (N^2). Que es más barato que min-cut, que mencionaste al intentarlo, así que supongo que es lo suficientemente barato para ti.

Answer 2

primero vemos que, las áreas pueden ser bloqueadas por una o dos cuadrículas adyacentes nunca estarán en la ruta más corta.

ver el caso en su ejemplo, son esas dos cuadrículas amarillas las que bloquean los puntos.

bloqueado por una rejilla es fácil de entender. Cuando bloqueado por dos:

1. si no adyacente, podemos añadir paredes adicionales para que sea el único camino, ir en a través de uno y salir de la otra, por lo que es posible que tengamos los las interiores.
2. si está adyacente, siempre podemos ir de uno directamente al otro, por lo que todavía no necesitamos las cuadrículas dentro de esa área.

Así que aquí hay viene el algoritmo:

enumerar cada cuadrícula vacía

1. poner una pared en él y utilizar las inundaciones relleno para encontrar las áreas bloqueadas, que no sirven de nada.
2. intente poner una pared en una de sus cuatro cuadrículas adyacentes (si está vacía), use relleno de inundación para encontrar las áreas bloqueadas, no sirven de nada.