Hamiltonian path in grid graph
There isn't going to be a fast algorithm for this problem.

The class of graphs you're dealing with is, in some of the literature, called grid graphs.  That is, they're finite induced subgraphs of the infinite graph with vertices $\mathbb{Z}\times\mathbb{Z}$ with an edge from $(x,y)$ to $(x',y')$ if, and only if, $|x-x'|+|y-y'|=1$.

Itai, Papadimitriou and Szwarcfiter (Hamiltonian Paths in Grid Graphs, SIAM Journal on Computing, 11(4):676&ndash;686, 1982) showed that it's NP-complete to determine whether a grid graph has a Hamiltonian path. Your problem is NP-hard (under Cook reductions, and possibly also under the more usual Karp reductions): if you can determine the length of the longest path from a vertex, just do that for each vertex in turn and see if any of the longest paths is Hamiltonian.