As every cow does occasionally, Bessie has lost herself in the woods! She desperately needs to get back to the barn but has no idea where to go.
The woods can be thought of as an R x C grid (1 <= R <= 5; 1 <= C <= 5). Bessie is located in the lower left corner at row 1, column 1; the barn is located in the upper right corner at in row R, column C. Each square in the grid is either empty (denoted by '.') or blocked by a tree (denoted by 'T'). Bessie's square and the barn will always be empty.
From a given square, Bessie may move to any adjacent square (one that shares a long edge with Bessie's current square) as long as it is empty. As Bessie is quite a smart cow, she never visits a square twice on the way back to the barn.
Determine the number of different ways Bessie can take that lead her from her initial position back to the barn while visiting at most K different squares (1 <= K <= R * C).
By way of example, consider this forest:
Bessie has a number of ways to get to the upper right corner, here are all seven of them and their path lengths (the number of squares visited):
cdef ...f ..ef ..gh cdeh cdej ...f
bT.. .T.e .Td. .Tfe bTfg bTfi .Tde
a... abcd abc. abcd a... a.gh abc.
Length: 6 6 6 8 8 10 6