Proof for the length of the shortest 4-connected path and 8-connected path on a chessboard I have a chessboard with a square marked with A as in the following figure:
$$\begin{array}{|c|c|c|} \hline
8&1&2\\ \hline
7&A&3\\ \hline
6&5&4\\ \hline
\end{array}$$
The $4$-connected neighbors squares of A are marked with $1, 3, 5, 7$.
The $8$-connected neighbors squares of A are marked with $1, 2, 3, 4, 5, 6, 7, 8$.
Then I have a chessboard with two marked squares, an origin square and a destination square: a $4$-connected path from the origin to the destination is a sequence of squares that connects the origin to the destination and all the squares in the sequence are $4$-connected neighbors; an $8$-connected path from the origin to the destination is a sequence of squares that connects the origin  and the destination and all the squares in the sequence are $8$-connected neighbors. The length of a path is the number of squares in the sequence.
The left part of the following figure shows a $4$-connected path from the origin square marked with $1$ to the destination square marked with $7$; the length of the path is $7$. The right part of the figure shows an $8$-connected path from the origin $1$ to the destination $5$; the length of the path is $5$.
$$\begin{array}{}
\begin{array}{|c|c|c|} \hline
&6&7\\ \hline
&5&\\ \hline
&4&\\ \hline
&3&\\ \hline
1&2&\\ \hline
\end{array}&\qquad&\begin{array}{|c|c|c|} \hline
&&5\\ \hline
&4&\\ \hline
&3&\\ \hline
&2&\\ \hline
1&&\\ \hline
\end{array}
\end{array}$$
I have read in stackoverflow that the length of the shortest $4$-connected path between origin and destination is the Manhattan distance between origin and destination and that the length of the shortest $8$-connected path is the Chebyshev distance between origin and destination.
How to prove it?
 A: For the Manhattan distance, you can argue that the two directions are independent.  To get from $(a,b)$ to $(c,d)$ you need to move $|a-c|$ steps horizontally and $|b-d|$ steps vertically.  No move gives you both, so the distance is at least $|a-c|+|b-d|$.  If you do one and then the other, you construct a path that meets this minimum.
For the Chebyshev distance, you clearly need $\max (|a-c|,|b-d|)$ steps.  Now construct a path, starting with the correct number of diagonal steps, then the orthogonal steps in the remaining direction.
A: Impose a rectangular coordinate system that makes the lower left cell $\langle 0,0\rangle$ and the upper right cell $\langle m,n\rangle$, where $m$ identifies the column and $n$ the row. (In other words, in the example $m=2$ and $n=4$.) Any $4$-connected path from $\langle 0,0\rangle$ to $\langle m,n\rangle$ must take at least $m$ steps to the right and at least $n$ steps up, so it must have length at least $m+n$. On the other hand, it’s clear that any step down or to the left is wasted, since it must be compensated for by an extra step up or to the right, so $m+n$ is the minimum length of a $4$-connected path from $\langle 0,0\rangle$ to $\langle m,n\rangle$. Clearly $m+n=|m-0|+|n-0|$, the Manhattan distance between $\langle 0,0\rangle$ and $\langle m,n\rangle$.
Suppose that $m\le n$. From $\langle 0,0\rangle$ we can take $m$ steps up and to the right, reaching $\langle m,m\rangle$, and another $n-m$ steps up will take us to $\langle m,n\rangle$ in a total of $n$ steps. Similarly, if $m\ge n$ we can take $n$ steps up and to the right to $\langle n,n\rangle$ and then $m-n$ steps to the right, this time reaching $\langle m,n\rangle$ in $m$ steps. Thus, there is always an $8$-connected path of length $\max\{m,n\}$ from $\langle 0,0\rangle$ to $\langle m,n\rangle$. It only remains to show that there is no shorter $8$-connected path from $\langle 0,0\rangle$ to $\langle m,n\rangle$, since $\max\{m,n\}$ is the Chebyshev distance between $\langle 0,0\rangle$ and $\langle m,n\rangle$.
Suppose that $m\le n$, so that $\max\{m,n\}=n$; the other case is completely similar. Each step changes each coordinate by at most $1$, so that if $r$ steps take you to $\langle k,\ell\rangle$, then $k,\ell\le r$. In particular, if $r<n$, then $\ell<n$, and you cannot reach $\langle m,n\rangle$ in $r$ steps. Thus, at least $n$ steps are required.
