Instead of dfs I would've used dp. DP[i][j] is true if it's a guaranteed victory when you start from here, and false if it's a guaranteed loss.

Notice that: DP[i][j] = (false || !DP[i + 1][j — 2] || !DP[i — 1][j — 2] || !DP[i — 2][j — 1] || !DP[i — 2][j + 1])

The reason for the "!" symbol is because if you're at the current state, then you want to have at least one reachable cell so that its value is false, meaning that when you reach there, the opponent has a guaranteed loss.

The way to build the DP is going diagonally instead of the usual row by row, simply because while you can move from a row to a higher one (and similarly with columns), you will always move from a point (x, y) to a point whose coordinates' sum is less than x + y. So first build the cells with (i + j = 0), then (i + j = 1) and so on.

Additionally, after I made the DP, I looked at the table and noticed the property: You lose if and only if (x — 1) % 4 and (y — 1) % 4 both are smaller than 2.