What if this problem had the additional requirement that a path could not visit the same cell twice? So for example 2 in the original question the 'move three times' path would not be possible because the middle cell is visited twice.

Is an algorithm with efficient time complexity (i.e. polynomial time) still possible in this case?

(I'm asking because I originally misread the question to have this requirement, and I could not come up with an efficient solution).