A typical dynamic programming example is the snake sequence. Given a grid of numbers, find maximum length snake sequence and print it. A snake sequence is made up of adjacent numbers in the grid such that for each number, the number on the right or the number below it is $+1$ or $-1$ its value. For example, if you are at location $(x,y)$ in the grid, you can either move right i.e. $(x+1,y)$ if that number is $\pm 1$ or move down i.e. $(x,y+1)$ if that number is $\pm 1$. The length of a snake sequence is defined as the number of moves. Given the following grid (a matrix with $M$ rows and $N$ columns),

$\begin{matrix}9 & 6 & 5 & 2\\8 & 7 & 6 & 5\\7 & 3 & 1 & 6\\1 & 1 & 1 & 7\end{matrix}$

(a) The maximum LENGTH of snake sequence is: (A) 6 (B) 7 (C) 5 (D) 4

(b) Time complexity of above solution is: (A) $O(M\times N)$ (B) $O(M^2)$ (C) $O(N^2)$ (D) $O(M)$

(c) The last number of the maximum-length snake sequence is: (A) 9(0,0) (B) 6(3,2) (C) 7(3,3) (D) 1(2,3) (E) 7(0,2)

(d) The third number of the maximum-length snake sequence is: (A) 7(1,1) (B) 7(0,2) (C) 3(1,2) (D) 6(2,1) (E) 8(0,1)

（座標標示方式為 (row, column)，從0開始）