Cómo resolver este problema SPOJ

Este problema se trata simplemente de encontrar el diámetro en un árbol.
Como se menciona que hay exactamente un camino entre dos libres
bloques Por lo tanto, hay una estructura de árbol subyacente en la cuadrícula, cuyo
diámetro que necesitamos encontrar.
Por lo tanto, el procedimiento estándar para encontrar el diámetro de un árbol es
1. Elija cualquier bloque libre arbitrario (nodo de lectura).
2. Encuentre el nodo a la mayor distancia del nodo seleccionado.
(Esto se puede hacer en una llamada de BFS / DFS, es decir, en O (V))
3. Ahora con el nuevo nodo como nodo inicial, encuentre la longitud del más largo
ruta a partir de ella que nuevamente se puede hacer en una llamada de BFS / DFS iein O (V)
Por lo tanto, la complejidad general es dos llamadas de O (V), lo que lo convierte en O (V).
Dado que para el problema anterior R, C <= 1000, tenemos Vmax = 10 ^ 6.
Por lo tanto, el problema se puede resolver fácilmente utilizando el enfoque mencionado anteriormente.