Re: how to solve this problem

I will tell you the solution because this problem should have time limit of around 3-5 seconds. I struggled for almost two days making that algo suffice all tests, and still I had to precompute an empty 12x12 grid, and my AC solution ran for exactly 1 second :))

Go row-by-row with state representing connected components above. These will be something like 11022, 12021, 10220133, etc... Where 0 stands for no exit from above and 1..n stand for connected component number. Actually, every connected component will have exactly two exits downwards, and they will be placed in stack order. Cases like 1212 are impossible because it would mean that paths 1..1 and 2..2 intersect somewhere above. So, this gives us a way to effectively enumerate all of components using at most 2^2 * 3^10 states. Digit 0 means skip. Digit 1 means start new component. Digit 2 means close last open component (remeber their stack order). First digit can't be 2 and last digit can't be 1.

This is enough to keep values about previous and next row with cache of next_x[12] - a matching of exits for each column. Also, don't forget to keep array of indices with non-zero values for previous and the next row, this optimizes things a little as you will run only through reachable states.

Once you complete current row, paint everything to find resulting components matching with exits from the row just painted. It can be done via BFS, but I couldn't meet TL with that, so I had to optimize it - all paths are chains, so just walk straight. For the last row a path should be a chain loop covering of all upper exits.

Internal transfers should keep all components alive, that is - there must be no loops. This also allows to optimize recursive steps for building current row by remembering last connected upper component connected by "rhhhh..." - so just don't allow closing it towards itself, unless it is the last row.

Also, do not forget to skip first and last rows full of **********.