We will solve the task by using dynamic programming. We fill the grid row by row (row-major order). Let's assume we have completely covered the first three rows. Notice that we don't care exactly how is the upper part of the grid filled, we only need to know some information, as the dynamic programming paradigm suggests.

For each column, we keep track of whether there is a pipe opened towards the fourth row. To be more precise, we will describe our current state as a tuple with the number of elements equal to the number of columns. Each element can be either of:

• ~0~ – there is no pipe placed in this cell, or this pipe is not pointing towards the next row
• ~1~ – pipe is pointing down, and it is connected to the water source. Notice that there is at most one cell of this type at any moment.
• ~2~ and above – pipe is pointing down, but it's not connected to the water source. We are labeling connected components in this way. Notice that each number can appear either ~0~ or ~2~ times in some tuple.

In order to efficiently implement this solution, we have to normalize our tuples. Notice that the tuples ~(1, 5, 2, 0, 5, 2)~ and ~(1, 2, 3, 0, 2, 3)~ are equivalent, and we have to find a way to hash them to the same value.

So, we use memoization and count the requested number of ways. It's not easy to derive a precise complexity analysis. Taking into consideration the planarity of the pipe network, it's possible to prove that the number of tuples will be less than ~6n^3 \times 3^n~, which leads to ~3 \times 10^8~ for ~N = 10~. In reality, the number of states is considerably less.