Minimum number of steps required to visit every corner of a rectangular grid

Question

I am stucked at this problem:

---

Suppose we have the following grid configuration (or matrix) $G\in \Bbb{M}^{\{0,x,y\}}_{m\times n}$

(I.e $G$ is a matrix that have $m$ rows and $n$ colums over the alphabet $\{0,x,y\}$) $$G= \begin{bmatrix} x & 0 & 0 & \cdots & x \\ 0 & 0 & 0 & \cdots & 0 \\ 0 & y & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ x & 0& 0& \cdots & x \end{bmatrix} $$

What is the minimal number of steps required for $y$ to visit each of the corners of the grid (I.e.each of the $x$'s in the matrix) where $y$ can move left, right, up and down one cell at a time?

(The $y$ in the grid $G$ was arbitrarily placed, $y$ can be anywhere on the matrix including on the corners).

---

My try :

The minimum number of steps required for $y$ to visit each of the corners of the grid is at least the sum of manhattan distances from $y$ to each of the corners of the grid, since the minimal number of steps required to reach each corner of the grid is equal to the manhattan distance to that corner, we get that the sum of these distances will be the minimal number of steps required to reach each one of the corners.

Unfortunatley my answer is wrong.

If I take for example the grid: $$G= \begin{bmatrix} x & 0 & 0 & 0 & 0 & x \\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & y & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ x & 0 & 0 & 0 & 0 & x \end{bmatrix} $$

We can see that the minimal number of steps required is actully 19 and not the sum of the manhattan distances which is 20.

---

Thanks for any hint or help.

(Note: I've encountered this problem while trying to figure out a heuristic for $A^*$ grid search that calculates a path for $y$ that must visit each of the corners of a grid at least once)

Answer 1

The solution is to use a greedy approach. Always visit the corner whose Manhattan distance is the least and then visit the other 3 corners while grazing along the edges of the matrix.

The intuition is that we should minimize the number of steps we repeat in any particular direction.

Let the (Manhattan) distance you travel to move to a corner be $\Delta x + \Delta y$. One you are at the corner, the optimal way is to move across the edges of the matrix since (by the triangle inequality) any other sequence will be suboptimal. While grazing along the edges the distance that you will repeat is $s = \Delta x + \Delta y$ so our objective is to minimize $s$

Answer 2

Actually I think there is a relatively simple formula for this (it fits on one line) if you don't mind a few applications of the $\min(\cdot,\cdot)$ function.

Let the rows of the grid be numbered $1$ through $m$, the columns numbered $1$ through $n$. Let the starting position $y$ be in row $j$ and column $k$, and denote this position by the coordinates $(j,k)$.

The answer by Banach Tarski gives you the correct strategy to minimize the total number of steps. We start by finding the distances to all corners and then choose the closest corner.

To get to a corner, we can either go up $j - 1$ rows or down $m - j$ rows; and independently of the choice of up or down, we can either go left $k - 1$ columns or right $n - k$ columns. Whichever corner we choose, the number of steps is simply the sum of the number of rows to travel and the number of columns to travel. The Manhattan distance to the closest corner is therefore $$ \min(j - 1, m - j) + \min(k - 1, n - k). \tag1 $$

After we reach the corner, we visit the next three corners by traversing the edges of the grid. Once we have chosen the next corner to visit, the rest of the path is determined. We will do one of the following:

• up (or down) $m-1$ rows, then left (or right) $n-1$ columns, then down (or up) $m-1$ rows to the last corner, a total of $2m + n - 3$ steps.
• left (or right) $n-1$ columns, then up (or down) $m-1$ rows, then right (or left) $n-1$ columns to the last corner, a total of $m + 2n - 3$ steps.

Clearly, $2m + n - 3 < m + 2n - 3$ if and only if $m < n$; in fact, $2m + n - 3 = (m + n - 3) + m$ and $m + 2n - 3 = (m + n - 3) + n$. So the remaining number of steps, which is the lesser of these two quantities, is $$ (m + n - 3) + \min(m,n). \tag 2 $$

To find the total number of steps, we add expressions $(1)$ and $(2)$ together: $$ (m + n - 3) + \min(m,n) + \min(j - 1, m - j) + \min(k - 1, n - k). $$

If you would prefer to use absolute values rather than $\min(\cdot,\cdot)$, you can use the following identity equation: $$ \min(a,b) = \tfrac12(x + y - \lvert x - y \rvert). $$

The total distance then comes to $$ (m + n - 3) + \tfrac12(m + n - \lvert m - n \rvert) + \tfrac12(m - 1 - \lvert m - 2j + 1 \rvert) + \tfrac12(n - 1 - \lvert n - 2k + 1 \rvert) $$ which simplifies to $$ 2m + 2n - 4 - \tfrac12(\lvert m - n \rvert + \lvert m - 2j + 1 \rvert + \lvert n - 2k + 1 \rvert). $$

Answer 3

Here's a algorithmic solution to finding the number of minimal number of steps required to travel to each one of the corners of the matrix at least once:

(For an efficient way to calculate the value see the answer of David K)

The algorithm is called FindMinimalNumberOfStepsToVisitAllCorners where corners is a set of 2D non-negative integer component vectors and position is a 2D non-negative integer component vector that indicates the starting position in the grid:

// Returns the closest corner in the set 'corners' to 'position'.
FindMinimalCorner(position, corners)
    minimalCorner = null
    minimalDistance = 0

    for each corner in corners
        if minimalCorner = null
            minimalCorner = corner
            minimalDistance = manhattanDistnace(position, corner)
        else
            if  minimalDistance > manhattanDistnace(position, corner)
                minimalCorner = corner
                minimalDistance = manhattanDistnace(position, corner)

    return (minimalCorner, minimalDistance)

// Returns the minimal number of steps required to visit all 'corners' from 'firstPosition'.
FindMinimalNumberOfStepsToVisitAllCorners(firstPosition, corners)
    sumOfDistances = 0
    position = firstPosition

    while corners != EMPTY_SET
        (minimalCorner, minimalDistance) = FindMinimalCorner(position, corners)

        sumOfDistances = sumOfDistances  + minimalDistance

        position = minimalCorner
        corners = corners - {minimalCorner}

    return sumOfDistances