← All solutions

This problem has a somewhat standard, but very complicated, dynamic programming solution, making it one of the hardest problems in the set.

The important observation is that, once we have filled in C’s in the first r rows, the only thing which matters for how we can complete the channel is the set of C’s in row r, and how they are interconnected.

As an example, consider the following case:

.##...
......
#.....
......

Now suppose that the first two rows are filled in as follows:

C##CCC
CC.C.C
??????
??????

We see that the C’s in columns 2, 4 and 6 are loose ends, and that the one in column 1 is not. Furthermore, the loose ends in columns 4 and 6 are connected to each other, and the one in column 2 leads to the origin of the channel. In general, the loose ends will always behave like this: there will be one loose end leading to the channel, and the remaining loose ends have to pair up with each other (otherwise there can be no way to complete the picture into a valid channel). Thus, in order to describe the current state, it suffices to describe:

• The set of columns with C’s in them.
• Which C is the loose end leading to the origin.
• Which other C’s are loose ends and how they pair up.