Me pareció un problema interesante e ideé una solución para el caso simple de un cuadrado inicial en llamas, aunque creo que esta solución puede extenderse a cualquier número de cuadrados iniciales en llamas.
En un nivel alto, descompuse este problema en un subproblema que sabía que podía resolver siempre. Para ello, hallé la cantidad de tiempo para llenar el campo si el cuadrado inicial de "fuego" estaba en una de las cuatro esquinas. Utilizando el $L_1$ (o métrica de la distancia de los taxis, como se ha mencionado anteriormente) esto se convierte en algo trivial.
Para cualquier matriz $M$ de tamaño $(n,m)$ Dado que una esquina singular está en llamas, el tiempo $t$ que se necesita para llenar toda la matriz viene dada por: $t=n+m-2$ . Se trata de una aplicación directa de la $L_1$ distancia, donde restamos dos, una por la casilla inicial en llamas y otra por la esquina para que no cuente doble. Escribiendo un pequeño ejemplo de algo menor que $(10x10)$ me ayudó a ver lo que estaba pasando.
A partir de ahí, nos damos cuenta de que si un solo cuadrado empieza a arder en cualquier parte de nuestra matriz/campo, podemos romper nuestra matriz $M$ en 4 subcampos, donde cada uno tiene una esquina singular en llamas. A partir de ahí sabemos el tiempo que tardará en arder cada uno de los cuatro subcampos, que podemos llamar $t_1, t_2, t_3,$ y $t_4$ . Así, el tiempo mínimo que tarda en arder todo el campo va a ser el subcampo que más tiempo arde, definido como $max(t_1, t_2, t_3, t_4)$ .
No le dediqué mucho tiempo, pero después de codificar tanto el problema como mi solución y ejecutarla 1000 veces con tamaños de campo y puntos iniciales generados aleatoriamente, funcionó siempre.
Creo que este problema también tiene relación con Células Voroni Y creo que esta solución podría adaptarse a múltiples puntos de partida.
