Similar to the editorial, we observe that we need to cut $$$(1, 1)$$$ from $$$(n, n)$$$ with a simple path along door and wall grid edges that passes from the upper-right border through A and B to the lower-left border. Further, its three segments -- UR $$$\rightarrow$$$ X0, X1 $$$\rightarrow$$$ Y0, Y1 $$$\rightarrow$$$ LL -- should not be connected by wall grid edges. So, we can merge grid corner vertices into connected components. Minimizing the number of doors along the path while ensuring that each component is used in at most one segment gives the correct answer.

The basic idea of a randomized solution is that we can randomly colour vertices with three colours, and then search for the shortest segments only visiting vertices of the correct colour. An improvement to this is to search for the segments sequentially. For the first segment, we can use a random bi-colouring, defining currently allowed and currently forbidden vertices. For the second, ensure that the already visited vertices are not reused, and for the others generate a new bi-colouring. For the third segment, every remaining vertex is allowed. If the third segment is the longest in the correct answer, we avoid many of the constraints and only need each of the first two segments to be coloured as allowed on their turns, and additionally to colour a few other vertices as forbidden to make every bad choice of a segment either blocked or too costly.

However, this could only work if the answer had a small cost, for example if each edge was either a door or a wall, and even then it would require carefully tuning or randomly sampling probabilities of "allowed" and "forbidden" colours. Instead of using two discrete colours we can assign a random priority to each vertex, representing its degree of forbidden-ness, and when searching for a segment of the path first minimize the maximum used priority, then minimize the path length. If we needed to colour some vertices allowed and some forbidden, now we only need the former to have lower priorities than the latter. This achieves the effect of choosing the optimal colour probabilities and should slightly improve the probability of success. While there is a chance that a longer path might be preferred because it has a smaller maximum priority, this is not overly likely since that path has to bypass a specific maximum-priority vertex and, being longer, not encounter an even worse vertex.

The final solution is:

1. Select the number of iterations based on the cost of an iteration $$$\sim (n+1)^2$$$ and the time budget of the current test case $$$\sim \dfrac{n^4}{N^4}$$$.
2. Each iteration, pick one of the 8 types of paths (A then B, or B then A; A0 then A1, or A1 then A0; B0 then B1, or B1 then B0) and one of the 6 permutations of the three path segments.
3. For each of the first two segments, first find the minimax priority of a path, then find the minimum cost path with that priority, forbidding vertices used earlier and vertices absolutely necessary later. Priorities can either be sampled independently for the two segments or sampled once and reused by inverting them (both approaches seem to work, reusing but not inverting seems not to [UPD: there was a bug, reusing but not inverting also works]).
4. Find the shortest third segment and relax the answer, continue to the next iteration.

Does it really have a good worst-case success probability, or is there a counter-test?