Separating the snakes
This can be solved in polynomial time.

Say that in the input we are given the number of snakes $n$ and for every snake the squares it occupies. Let $m$ denote the total number of squares in all snakes. Assume every snake occupies at least three squares. 

If no square has $x$-coordinate in some interval $[a, b]$, we can compress that interval into a single point. Then, the squares have coordinates in range $[0, 2m - 1]$. We will do DP in $\mathcal{O}(m^{5})$.

We calculate a DP with a state for every rectangle $(x_{0}, y_{0}), (x_{1}, y_{1})$.

We say that some snake is inside the rectangle if at least two of its squares are inside the rectangle. If at least two of some snake's squares are outside the rectangle, we say it is outside the rectangle. Notice that a snake can be both inside and outside the rectangle.

Say there are $k$ snakes inside the rectangle. The DP will represent whether we can separate the $k$ snakes with at most $k-1$ fences while obeying the trimming rules.

If any snake is both inside and outside the rectangle, we automatically fail and set $DP[x_{0}, y_{0}, x_{1}, y_{1}] = 0$. If only one snake is inside the rectangle, we set $DP[x_{0}, y_{0}, x_{1}, y_{1}] = 1$.

Otherwise, for every $x_{0} &lt; x &lt; x_{1}$, we will try to add a fence at this $x$-coordinate. If $DP[x_{0}, y_{0}, x, y_{1}]$ and $DP[x, y_{0}, x_{1}, y_{1}]$ and no snake inside the rectangle is outside of both of the two rectangles the fence splits our rectangle to, the fence works and we set the value of the DP to true. We similarly loop $y$-coordinates inside the rectangle. If no working fence was found, we set the DP to false.

In the end, the algorithm outputs $DP[0, 0, 2m-1, 2m-1]$

This DP can be optimised to $\mathcal{O}(n^{5} + m)$ by trimming states from the DP. We can assume that the DP-box doesn't start or end with an empty column or row, therefore there has to exist some snake with the leftmost square in the box, and we can store $x_{0}$ as the index of that snake, and whether the leftmost square in the box is the leftmost or second leftmost square of that snake (It cannot be any square after that, since then the snake would be outside the box). Storing $y_{0}, x_{1}, y_{1}$ similarly gives us $\mathcal{O}(n^{4})$ dp-states. We can further loop the $x$-coordinate of a fence over just the first and last $x$-coordinates of squares of snakes in the rectangle plus minus at most one, as every other fence either trims too much from a snake or would be equivalent to a fence placed directly to the left of it. Loop similarly over $y$. The number of such coordinates is $\mathcal{O}(n)$.