CodeShell.kr - Check-in

Challenge

42×42 迷宫，20 个打卡站。难度在于这是最短哈密顿路径问题，而且并列时要取字典序最小，需要两套独立实现交叉验证。

Find your way out

找到出去的路。

https://codeshell.kr/challenges/misc-checkin/

Solution

附件 floorplan.txt 是 42×42 迷宫，@ 入口、$ 出口、A–T 共 20 个打卡站。要求恰好访问每个站一次后出口，步数最少；并列时取字典序最小的访问顺序。

Step 1：对全部 22 个关键点（20 站 + 入口 + 出口）做 BFS，得到 22×22 距离矩阵。

Step 2：这是 20 节点的最短哈密顿路径，用 Held-Karp 位掩码 DP：g[mask][i] = 从站点 i 出发访问完 mask 再走到出口的最小步数。2^20 × 20 的状态在 C 里约 1 秒。

Step 3：字典序最小：逐步贪心，每一步选编号最小、且使「剩余代价恰好等于最优值」的站点。

optimal steps: 227
order: GPKTEOQBSCDLMINFAHJR

Step 4：用正向递推（dp[mask][i] = 从入口出发访问 mask 且停在 i）独立实现第二遍，同样得 227，并复核该顺序实际走满 20 站、总步数 227。起点选项也打印出来核对：只有 G 与 P 能取到 227，G 更小，与字典序规则一致。

Script

#!/usr/bin/env python3
"""CodeShell.kr — misc-checkin: BFS distances between stations.

Grid: '#' wall, '.' open, '@' entrance, '$' exit, 'A'-'T' stations.
Emits a 22x22 integer matrix (0-19 = stations A-T, 20 = '@', 21 = '$').

Usage: uv run python solvers/checkin_dist.py > checkin_dist.txt
"""

import sys
from collections import deque
from pathlib import Path

GRID = "extracted/misc-checkin/floorplan.txt"


def main():
    lines = [l for l in Path(GRID).read_text().splitlines() if l]
    h, w = len(lines), len(lines[0])

    pos = {}
    for y, row in enumerate(lines):
        for x, c in enumerate(row):
            if c in "@$" or "A" <= c <= "T":
                pos[c] = (x, y)

    names = [chr(ord("A") + i) for i in range(20)] + ["@", "$"]
    assert all(n in pos for n in names), "missing markers"

    def bfs(start):
        dist = {start: 0}
        q = deque([start])
        while q:
            x, y = q.popleft()
            for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nx, ny = x + dx, y + dy
                if 0 <= nx < w and 0 <= ny < h and lines[ny][nx] != "#" and (nx, ny) not in dist:
                    dist[(nx, ny)] = dist[(x, y)] + 1
                    q.append((nx, ny))
        return dist

    cache = {n: bfs(pos[n]) for n in names}
    m = len(names)
    out = []
    for a in names:
        row = []
        for b in names:
            row.append(cache[a].get(pos[b], -1))
        out.append(row)

    # sanity: distances must be symmetric and finite
    for i in range(m):
        for j in range(m):
            assert out[i][j] >= 0, f"unreachable {names[i]} -> {names[j]}"
            assert out[i][j] == out[j][i], "asymmetric"
    assert all(out[i][i] == 0 for i in range(m))

    print("\n".join(" ".join(str(v) for v in row) for row in out), file=sys.stdout)
    print(f"# stations={m}", file=sys.stderr)


if __name__ == "__main__":
    main()

/* CodeShell.kr — misc-checkin: Held-Karp shortest Hamiltonian path.
 *
 * Reads a 22x22 distance matrix (0-19 = stations A-T, 20 = '@', 21 = '$')
 * from stdin. Finds the shortest walk @ -> visit each station exactly once
 * -> $, and among all optimal walks the lexicographically first station
 * order (A..T = 0..19).
 *
 * build: gcc -O2 -o checkin_tsp checkin_tsp.c
 */
#include <stdio.h>
#include <stdlib.h>

#define N 20
#define M 22
#define FULL ((1 << N) - 1)
#define INF 1000000000

static int d[M][M];
static int *g; /* g[mask*N + i] = min cost from i, visiting all of mask, then exit */
#define G(mask, i) g[(size_t)(mask) * N + (i)]

int main(void) {
    for (int i = 0; i < M; i++)
        for (int j = 0; j < M; j++)
            if (scanf("%d", &d[i][j]) != 1) { fprintf(stderr, "bad matrix\n"); return 1; }

    size_t sz = (size_t)(1 << N) * N;
    g = malloc(sz * sizeof(int));
    if (!g) { fprintf(stderr, "oom\n"); return 1; }

    for (int i = 0; i < N; i++) G(0, i) = d[i][21];

    for (int mask = 1; mask <= FULL; mask++) {
        for (int i = 0; i < N; i++) {
            if (mask & (1 << i)) continue; /* i must not be in mask */
            int best = INF;
            for (int j = 0; j < N; j++) {
                if (!(mask & (1 << j))) continue;
                int v = d[i][j] + G(mask ^ (1 << j), j);
                if (v < best) best = v;
            }
            G(mask, i) = best;
        }
    }

    int best = INF;
    for (int j = 0; j < N; j++) {
        int v = d[20][j] + G(FULL ^ (1 << j), j);
        if (v < best) best = v;
    }
    printf("optimal steps: %d\n", best);

    printf("start options:");
    for (int j = 0; j < N; j++)
        printf(" %c=%d", 'A' + j, d[20][j] + G(FULL ^ (1 << j), j));
    putchar('\n');

    int cur = 20, R = FULL, f = best, seq[N];
    for (int k = 0; k < N; k++) {
        for (int j = 0; j < N; j++) {
            if (!(R & (1 << j))) continue;
            int rem = R ^ (1 << j);
            int cost = G(rem, j);
            if (d[cur][j] + cost == f) {
                seq[k] = j; f = cost; cur = j; R = rem;
                break;
            }
        }
    }

    printf("order: ");
    for (int k = 0; k < N; k++) putchar('A' + seq[k]);
    putchar('\n');
    return 0;
}

CodeShell{GPKTEOQBSCDLMINFAHJR}