Some time back I was interviewed at Google. And this question threw me off and probably made me blank. Interviewer will not say anything more than:

You have an array of grid and there is a horse at bottom left (n-1, 0) and the horse has to go to bottom right corner (n-1, m-1). The horse can go in all 8 directions. Find out all the ways it can reach to other corner. The thing that was not clear to me was was this grid bounded (of course it should be). I thought of all DP, back tracking etc. Eventually came out with a brute force way to starting in all 8 directions (if possible) and if reached destination do a count++. I believe interviewer was looking for something else.

I will safely assume that a visted cell should not be visited again. The mental block I faced was how to come up with a DP relationship. /, \ path kind of makes it hard to come out with recurring solution. Also typically grid problems I practiced was around one end of diagonal to another and not like these. And I can't find this question anywhere. Probably there is nothing better than brute force but hard to believe.

Any clues?