Find the longest snake on a grid Background

A snake is a path over the cells of a square grid, such that it doesn't touch itself on a side of a unit square. Touching at a corner is allowed.

An example snake:

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


Some example non-snakes:

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

###
.#.

##
##


Challenge

Given an empty grid with the two endpoints of a snake marked on it, find the longest possible snake that fits on the grid. If there are multiple answers having the same length, you may choose to output one or all of them.

The input can be given as a character matrix (or equivalent) with two endpoints marked on it, or the dimensions (width, height) and the coordinates of the endpoints. You may choose to output the grid containing the snake or a list of coordinates of cells occupied by the snake (or equivalent).

Standard code-golf rules apply. The shortest code in bytes wins.

Example I/O

Each I/O example is given as a character matrix, # being the part of the snake.

Input:
..#...#...
Output:
..#####...

Input: (corner case)
......
......
..##..
......
......
......
Output: same as input (no way to get longer without violating no-touch condition)

Input:
..#.#
.....
.....
.....
Output:
###.#
#...#
#...#
#####

Input:
#....
.....
.....
.....
....#
Output:
#####
....#
#####
#....
#####
Python 3.8 (pre-release), 207 194 181 bytes

-7 bytes thanks to @ovs

Input

The width \$ w \$, the height \$ h \$, the starting point \$ s \$, and the ending point \$ e \$. \$ s \$ and \$ e \$ are complex numbers which represent the coordinates of the endpoints. 

Output

A list of points, in the form of complex numbers.





C={1,-1,1j,-1j}
def f(w,h,s,e):P=[[s]];exec("P=[j+[t+(t==e==(A:=j+[t]))]for j in P for k in C if w&gt;(t:=j[-1]+k).real&gt;-1&lt;t.imag&lt;h&gt;0&lt;all({t+l}-{*j}for l in{0}|C-{-k})];"*w*h);return A


Try it online!

Explanation

We use a breadth-first search to search for all possible snakes, starting at \$ s \$, making sure that the next tile is not adjacent to any previous tile, and that we do not go past the boundary. After each iteration, we check for all paths whose last element is \$ e \$, meaning that we have found a complete path from \$ s \$ to \$ e \$. Instead of storing all complete paths and returning the one with maximum length, we can simply return the last path found, since breadth-first search already searches for paths by length.