For every room ~R~, let the "parent" room be the room before ~R~ such that there could be a wall between ~R~ and the room. For example, the parent of ~8~ is ~1~, the parent of ~16~ is ~5~ etc. Not all rooms have parents, ~5~ and ~26~ are examples of this. The first part of any solution is to find a way to determine the parent of a given room, since this is required to parse the input.

There is more than one way to do this, presumably all of which involve some math on the room numbers to achieve complexity better than ~\mathcal O(R)~.

Here is a solution of complexity ~\mathcal O(\log R)~. Let ~corner(n)~ be the ~n^\text{th}~ "corner" room (corner room ~0~ is room ~1~; the others are ~2, 3, 5, 7, 10, 13, 17, \dots~). It can be shown that ~corner(n) = \frac{n+2}{2} \times \frac{n+1}{2} + 1~, with division rounding down. We can use binary search to find the largest ~n~ such that ~corner(n)~ is less than ~R~. The parent of ~R~ is then ~R-(corner(n)-corner(n-4))-1~.

We can also calculate the parent room in ~\mathcal O(1)~. If we group the rooms into groups of sizes ~2, 4, 6, 8, 10, \dots~, then group ~2n+1~ begins with room ~n^2+n+1~. From this, it is rather obvious that room ~x~ is in group ~\lfloor \frac{-1+\sqrt{4x-3}}{2} \rfloor~, and from this we can calculate the parent of room ~x~, depending on whether the room is in the first or second half of its group.

The graph is now implicitly constructed, but is still too big to manipulate. Notice that almost all rooms are incidental to exactly two edges, connecting them to the rooms right before and right after them. The exceptions are rooms at both sides of a broken wall – these have three or four edges. We can compress the trivial nodes to make a weighted graph with ~\mathcal O(K)~ vertices and ~\mathcal O(K)~ edges, where the vertices are rooms ~1~, ~N~, and all rooms at both sides of a wall. Running Dijkstra's shortest path algorithm on this graph yields a solution of complexity ~\mathcal O(K \log K)~.