It's mentioned that

"one needs to be good at "ad hoc" problems as well as have good algorithmic knowledge."

My idea was:

• in each row, there are "good" intervals of cells that we can get to from (1, 1)

• a volcano splits a good interval into 2 (one or both possibly empty); if there's no volcano between 2 cells from different good intervals, they're merged (more generally, if we can get to some cell, we can get to all cells to its right until a volcano (or the border of the map)

• simulating this process efficiently (using set<>s for non-empty good intervals) for all rows is enough for comparably large n and m; for n large, merge chunks of empty rows into one

• there are at most O(m) non-empty good intervals; each volcano now leads to operations that take time; the same time is taken by merging 2 good intervals, and there are O(m) empty rows (after the above mentioned merging), so the time is

I think my idea is right but i overlooked something.

If you imagine a graph where each node is a volcane and two volcanes share an edge if they share a common point, then you only need to check if (1, 1) is cut-off from (n, n).

You do this my imagineing that walls are also nodes in the graph and checking if coresponding walls are connected.

Edit: nevermind i got it, where i was wrong.