# Finding simple path on grid graphs of length \$l\$

Let $$G$$ be a grid graph and we are given two vertices $$s$$ and $$t$$ and $$l$$, the goal is to check if there exists a path from $$s$$ to $$t$$ simple path of length $$l$$?

Brute force algorithm will give $$n^l$$ time algorithm as I will simply enumerate all the paths of length $$l$$. Are there faster algorithms for this problem?

My observation is grid graphs are bipartite graphs so all paths will be either of odd length or even length but I don’t know how to use this fact. Note that in grid graphs the degree is bounded by four so from any vertice to any other vertex, number of paths of length $$l$$ are bounded by $$4^l$$. I am looking for an algorithm faster than $$4^l$$.