Subtask 1

A simple BFS from ~(N, N)~ to ~(1, 1)~ is sufficient for this subtask. To reconstruct the lexicographically smallest shortest path, simply backtrack greedily, taking the lexicographically least character at each cell.

Time Complexity: ~\mathcal{O}(N^2)~

Subtask 2

For the full solution, we will need to make a couple of observations.

1. Either a path does not exist, or it will only move up or to the right. This can be proven in many ways by banking on the fact that every row and column has at most one blocked square, and will be left as a short exercise for the reader.

2. Diagonal chains of blocked cells that go from top-left to bottom-right can be represented by the smallest square that encloses it. Any path that passes through such a square can be easily replaced by a shorter path, so an optimal path will never pass through these squares.

3. There is some connected region in the bottom right of the grid for which we cannot reach ~(N, N)~ by only moving up or to the right (and thus, paths which cross through this region cannot be optimal). We may construct this region by taking the "shadow" cast by the blocked cell on column ~N~ (if it exists), propagating the shadow leftward through other blocked cells and bounding squares from observation ~2~. It is easy to see that any cell contained in this shadowed region cannot reach ~(N, N)~ by only moving up or to the right.

With these observations, we can simply block out the regions from observations ~2~ and ~3~ and then greedily construct a path (if it exists), taking R over U whenever possible since it is lexicographically smaller. To prevent degrading to ~\mathcal{O}(N^2)~ time complexity from maintaining these blocked regions, notice that we only have to maintain their outlines, which is on the order of ~\mathcal{O}(N)~. Depending on implementation, an extra log factor may be required.

Time Complexity: ~\mathcal{O}(N)~ or ~\mathcal{O}(N \log N)~