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.