Escape From Ayutthaya

Ayutthaya was one of the first kingdoms in Thailand, spanning since its foundation in 1350 to its collapse in 1767. The organization of Extraordinary Mystery Investigators (IME, in their language) aims to uncover the secrets of this ancient kingdom. One of IME's most notorious historians is Márcio "the indispensable" Himura. He is currently researching the laws and punishments in place during King Ramathibodi I's rule. Recent discoveries suggest how Ramathibodi I used to punish the subjects that did not convert to Theravada Buddhism, the religion he adopted.

The punishment involved trapping the accused prisoner in a room with a single exit and to light up a fire. If the prisoner could manage to reach the exit before getting caught on fire, she or he was forgiven and allowed to live. Márcio has access to some records that describe the floorplans of the rooms where this punishment took place. However, there are no documents asserting whether the prisoners were forgiven. Márcio would like to know whether each of these prisoners had any chance at all of having been forgiven. For that, Márcio represented each room as a grid with N rows and M columns, where each position has a symbol with the following meaning

where "start" is the person's initial position in the room when fire has been lit up. Moreover, Márcio imposed the following constraints in his model:

• Fire spreads in the four cardinal directions (N, S, E, O) at the speed of one cell per minute.
• The prisoners can also move in these four directions at the same speed.
• Neither fire nor the prisoners can walk through a wall.
• If the prisoner and fire occupy the same position at any instant, the prisoner dies instantaneously.

You are a member of IME and Márcio would like to know if you deserve your position. He has charged you with the task of determining whether a prisoner had any chance to be forgiven.