Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
This is the sort of problem which generally can't be solved efficiently, but given its structure, it should be a safe bet that some pattern to the answers will emerge for relatively small values of 
~C~, and extend to arbitrarily large values of ~C~. This proves to indeed be the case, and the pattern can be visually seen fairly easily if all of the answers up to around 
~C = 16~ are found (though guessing the pattern earlier, around 
~C = 13~, is also reasonable).
For such small values of ~C~, a brute force algorithm will suffice, though not just any one. The most natural approach is to try all 
~2^{4C}~ possible sets of walls on the grid, and for each one, find the furthest-away pair of empty cells using BFS in another 
~\mathcal O(C^2)~ time. This process is incredibly inefficient, but with a few optimizations, it can be made to successfully yield the answers up around ~C = 13~ in a reasonable amount of time – most likely not within the problem's time limit, but at least fast enough to run at home for a while, look at the answers, determine their pattern, and put together a solution with hardcoding.
A more elegant brute force algorithm exists which is both simpler, and can also produce the required answers within a few seconds. We can instead consider directly generating the path from the starting cell to the destination cell. We'll start from each possible starting cell, and repeatedly recurse to adjacent cells, while maintaining the cells which the path has already visited. The only requirement is that the path never visits a cell adjacent to an earlier cell on the path (aside from its previous cell). All cells which aren't on the path can then be filled in with walls to yield a valid grid.
In any case, it can then be seen that once ~C~ becomes large, optimal grids contain repeated instances of the following pattern of walls in the middle:
.#....
...###
###...
....#.
In particular, the answer for 
~C = 14~ is equivalent to the answer for 
~C = 8~ but with this pattern inserted once for a certain interval of its interior columns. In the same way, the answer for every 
~C > 14~ can be determined from the answer for a grid with 
~6~ fewer columns, meaning that only the answers for 
~C = 1 \dots 13~ must be computed from scratch.
Comments