Overview

On an \(N \times N\) grid, find the minimum number of moves to travel from a starting square \(S\) to an ending square \(T\) while passing through all \(M(\le 15)\) specified squares (in any order).

Analysis

• Since the robot can move one square at a time in the four cardinal directions, the shortest distance between two points is the “grid shortest distance without obstacles” = Manhattan distance.
  That is, given coordinates \((r,c)\), the distance is \(|r_1-r_2|+|c_1-c_2|\).
• The board size \(N\) can be up to \(10^5\), so the total number of squares \(N^2\) is enormous. Therefore, approaches like “BFS on the grid to find shortest paths” are impossible (the number of states is too large, causing TLE/memory overflow).
• However, the key observation is that we only need to visit \(M\) shelf squares, and \(M\le 15\) is small.
  Optimizing the entire path reduces to optimizing the visitation order of “\(S \to (\text{visit all shelves}) \to T\)”.
• Naively enumerating all visitation orders of the shelves gives \(M!\) possibilities. For example, when \(M=15\), \(15!\approx 1.3\times 10^{12}\), which is far too many.
• Therefore, we use “subset DP (bit DP)”, managing the visitation status of the shelf set with a bitmask to find the minimum (a classic approach for the Traveling Salesman Problem).

Algorithm

1. Convert square numbers to coordinates
   Square number \(k(1\le k\le N^2)\) is assigned in row-major order from the top-left, so:

   • The quotient of \(k-1\) divided by \(N\) is the row \(r\), and the remainder is the column \(c\)
     That is, \((r,c)=\text{divmod}(k-1, N)\) gives 0-indexed coordinates.

2. Precompute distances between relevant points
   The points to visit are \(S\), shelves \(P_1..P_M\), and \(T\), but only the following distances are needed for the DP:

   • \(dS[i] =\) distance\((S, P_i)\)
   • \(d[i][j] =\) distance\((P_i, P_j)\)
   • \(dT[i] =\) distance\((P_i, T)\)
     All of these are Manhattan distances computable in \(O(1)\).

3. Bit DP (Subset DP)

   • State: \(dp[mask][i]\)
     = “the minimum number of moves when all shelves in set \(mask\) (shelves whose bits are set have been visited) have been visited, and the robot is currently at shelf \(i\)”
   • Initialization: when shelf \(i\) is visited first
     \(dp[1<<i][i] = dS[i]\)
   • Transition: from state \(mask\) with the last visited shelf being \(i\), move to an unvisited shelf \(j\)
     $\(dp[mask\cup\{j\}][j] = \min\Big(dp[mask\cup\{j\}][j],\ dp[mask][i] + d[i][j]\Big)\)$
   • Answer: after visiting all shelves, move to \(T\)
     $\(\min_i \big(dp[full][i] + dT[i]\big)\)\( where \)full = (1<)-1$.

4. Special case when \(M=0\)
   If there are no shelves, simply output distance\((S,T)\) (Manhattan distance).

(Concrete example) If there are 3 shelves, \(mask\) ranges from \(0\) to \(7\). For example, \(mask=101_2\) means “shelves 0 and 2 have been visited”, and from there we transition to unvisited shelf 1 to get \(111_2\).

Complexity

• Time complexity:
  Distance precomputation is \(O(M^2)\). The DP has \(2^M \times M\) states with at most \(M\) transitions each, so
  $\(O(2^M \cdot M^2)\)\( (Fast enough for \)M\le 15$.)
• Space complexity:
  The DP table is \(2^M \times M\)
  $\(O(2^M \cdot M)\)$

Implementation Notes

• Be careful to use \(k-1\) for coordinate conversion: Since numbering starts from 1, use \((k-1)\) with divmod.

• Set INF to a large value: Use a sufficiently large value (e.g., \(10^{30}\)) as the initial value for the DP.

• Enumerating unvisited sets: Compute unvisited bits with rem = ((1<<M)-1) ^ mask, and extract the lowest set bit with lb = j & -j for efficient iteration.

• Large \(N\) is not a problem: We only work with the coordinates of \(S, T, P_i\), and the design does not require storing or searching the entire grid.

  Source Code

import sys

def coord(k, N):
    k -= 1
    return divmod(k, N)  # (r, c)

def manhattan(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    N = int(next(it))
    M = int(next(it))
    S = int(next(it))
    T = int(next(it))

    if M == 0:
        s = coord(S, N)
        t = coord(T, N)
        print(manhattan(s, t))
        return

    P = [int(next(it)) for _ in range(M)]

    s = coord(S, N)
    t = coord(T, N)
    pts = [coord(x, N) for x in P]

    dS = [manhattan(s, pts[i]) for i in range(M)]
    dT = [manhattan(pts[i], t) for i in range(M)]
    d = [[0] * M for _ in range(M)]
    for i in range(M):
        for j in range(M):
            d[i][j] = manhattan(pts[i], pts[j])

    INF = 10**30
    size = 1 << M
    dp = [[INF] * M for _ in range(size)]
    for i in range(M):
        dp[1 << i][i] = dS[i]

    for mask in range(size):
        row = dp[mask]
        for i in range(M):
            cur = row[i]
            if cur >= INF:
                continue
            rem = ((size - 1) ^ mask)
            j = rem
            while j:
                lb = j & -j
                nj = (lb.bit_length() - 1)
                nmask = mask | lb
                val = cur + d[i][nj]
                if val < dp[nmask][nj]:
                    dp[nmask][nj] = val
                j -= lb

    full = size - 1
    ans = min(dp[full][i] + dT[i] for i in range(M))
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.