Time complexity: \(O(m 2^{3n})\)
There is a solution in \(O(nm 2^{2n+3})\) The resulting sequence for \(N\times N\) grids can be found at OEIS.