So I came across this problem, and I could not solve it. Can I have some hints?

Given a n x m chess board, a starting position (r1, c1) and a target position (r2, c2), you have to output the maximum number of moves a chess knight can make to get to the target position. Each cell can only be visited once.

n and m were ~400.