题解 | 收集纸片

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_POINTS 12  // 起点 + 最多10个纸片 + 缓冲
#define INF INT_MAX
typedef struct 
{
    int x, y;
} Point;
int min(int a, int b) 
{
    return a < b ? a : b;
}
int manhattan(Point a, Point b) 
{
    return abs(a.x - b.x) + abs(a.y - b.y);
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int room_w, room_h;
        scanf("%d %d", &room_w, &room_h);
        Point start;
        scanf("%d %d", &start.x, &start.y);
        int n;
        scanf("%d", &n);
        Point points[MAX_POINTS];
        points[0] = start;
        for (int i = 1; i <= n; i++) {
            scanf("%d %d", &points[i].x, &points[i].y);
        }
        int N = n + 1;  // 总点数（起点 + 纸片）
        // 计算距离矩阵
        int dist[MAX_POINTS][MAX_POINTS];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                dist[i][j] = manhattan(points[i], points[j]);
            }
        }
        int dp[1 << MAX_POINTS][MAX_POINTS];
        for (int mask = 0; mask < (1 << N); mask++) {
            for (int i = 0; i < N; i++) {
                dp[mask][i] = INF;
            }
        }
        dp[1][0] = 0;
        for (int mask = 1; mask < (1 << N); mask++) {
            for (int i = 0; i < N; i++) {
                if (dp[mask][i] == INF) continue;
                if (!(mask & (1 << i))) continue;
                
                for (int j = 0; j < N; j++) {
                    if (mask & (1 << j)) continue;
                    
                    int new_mask = mask | (1 << j);
                    int new_dist = dp[mask][i] + dist[i][j];
                    
                    if (new_dist < dp[new_mask][j]) {
                        dp[new_mask][j] = new_dist;
                    }
                }
            }
        }
        // 找到回到起点的最短路径
        int full_mask = (1 << N) - 1;
        int ans = INF;
        for (int i = 0; i < N; i++) {
            if (dp[full_mask][i] != INF) {
                int total = dp[full_mask][i] + dist[i][0];
                if (total < ans) {
                    ans = total;
                }
            }
        }
        printf("The shortest path has length %d\n", ans);
    }
    return 0;
}