[Help] Fastest solution for this 2D grid jumping problem !!

Revision en1, by dang_252, 2021-05-16 20:41:07

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.

Details of my solution

Please show me a faster (possibly fastest) solution or some improvements that I can make to my algorithm. Thank so much <3 <3.

History

Revisions

Rev. Lang. By When Δ Comment
en1 dang_252 2021-05-16 20:41:07 1465 Initial revision (published)