Básicamente, la solución parece ser obvia si visualizamos el laberinto como un gráfico que tiene [matemática] N * M [/ matemática] número de nodos y cada celda [matemática] (i, j) [/ matemática] tiene bordes no dirigidos con celdas vacías vecinas, es decir, celdas [matemáticas] (i, j + 1), (i, j-1), (i + 1, j), (i-1, j). [/ matemáticas]
Ahora comenzamos desde la celda inicial dada y encontramos todos los ciclos que terminan en la misma celda. En el caso, podemos encontrar un ciclo de longitud> = k, luego concluimos la respuesta como “SÍ”, de lo contrario “NO”.
Por lo tanto, la pregunta se reduce a encontrar todos los ciclos posibles en un gráfico que comienza y termina en un nodo dado. Esto se puede lograr mediante un DFS (Profundidad primera búsqueda) . Por supuesto, la complejidad temporal de esta solución podría ser exponencial en el peor de los casos, pero los casos de prueba de este problema en particular nunca exploran el peor de los casos y la solución basada en DFS es aceptable para este problema.
- ¿Cuál es un buen algoritmo para generar un archipiélago en un mapa en particular?
- ¿Es un nodo raíz un nodo interno en una estructura de datos de árbol?
- Cómo aprender algoritmos de manera fácil
- ¿Cuál es su opinión sobre Interview Cake para resolver algoritmos?
- Es un método de retroceso para imprimir permutaciones de cadena. No entiendo de qué manera se produce el flujo de control, como después de encontrar el intercambio, el intercambio se llama luego permutar y luego nuevamente. ¿Esto no se me viene a la cabeza?
Referencia : ¿Cómo podemos encontrar todos los ciclos simples en un gráfico no dirigido de manera eficiente? ¿Cómo encuentro los puntos que forman un ciclo en un gráfico?
Pensándolo bien, puedo decir que no hay una solución alternativa posible que pueda dar la respuesta en tiempo polinómico. De hecho, si existiera la solución de la complejidad del tiempo polinomial, el problema del ciclo de Hamilton también podría resolverse en el tiempo polinomial, que de hecho es un problema NP-Hard a partir de ahora.
Eche un vistazo a este código de CA para saber cómo aplicar dfs a este problema.
