Given a $$$N \times N$$$ table, each cell $$$(x,y)$$$ has a value $$$a[x][y]$$$.
From cell $$$(x, y)$$$ we can jump to cell $$$(x_1,y_1)$$$ if both of these satisfy:
$$$a[x_1][y_1] > a[x][y]$$$
$$$($$$$$$|x - x_1|=1$$$ and $$$|y - y_1| > 1)$$$ or $$$($$$$$$|x - x_1|>1$$$ and $$$|y - y_1| =1)$$$.
Find the longest path (number of jumps) we can make, if we start at cell $$$(X_0, Y_0)$$$.
Input is $$$N, X_0, Y_0$$$ and the array $$$a$$$. $$$(N \leq 1500, a[i][j] \leq 10^6)$$$
Example:
4
1 1
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
Output: $$$3$$$ (The path is $$$(1,1) \Rightarrow (2, 3) \Rightarrow (4,2) \Rightarrow (3,4)$$$).
My current solution works in about $$$O(4 * N * N * log(N) + 10^6 * log(10^6))$$$, and it didn't pass the time limit in $$$1$$$ second.
Please show me a faster (possibly fastest) solution or some improvements that I can make to my algorithm. Thank so much <3 <3.