N×M 迷宮，起點 (1,1)，有若干寶藏（≤10）。求從起點出發收集所有寶藏的最短路徑長度。可上下左右移動，不可穿牆。若無法收集全輸出 -1，若起點即為寶藏且無其他寶藏輸出 0。
dist[i][j]。若任意兩關鍵點不可達，輸出 -1。dp[mask][i] 表示已收集寶藏集合為 mask，當前位於關鍵點 i 的最短路徑。初始 dp[1][0] = 0（起點編號 0，mask 第 0 位為 1）。轉移：dp[mask | (1<。 min_i dp[(1<<(K+1))-1][i]。#include
using namespace std;
const int MAXN = 105;
const int INF = 0x3f3f3f3f;
int N, M, grid[MAXN][MAXN];
int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
struct Point { int x, y; } poi[15];
int K; // 寶藏數
int dist[15][15];
int dp[1<<12][12];
int bfs(int s, int t) {
queue> q;
vector> vis(N+1, vector(M+1, false));
q.emplace(poi[s].x, poi[s].y, 0);
vis[poi[s].x][poi[s].y] = true;
while (!q.empty()) {
auto [x, y, d] = q.front(); q.pop();
if (x == poi[t].x && y == poi[t].y) return d;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || nx > N || ny < 1 || ny > M) continue;
if (grid[nx][ny] < 0 || vis[nx][ny]) continue;
vis[nx][ny] = true;
q.emplace(nx, ny, d+1);
}
}
return -1;
}
int main() {
while (cin >> N >> M) {
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j)
cin >> grid[i][j];
K = 0;
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j)
if (grid[i][j] > 0) poi[++K] = {i, j};
if (K == 0) { cout << 0 << endl; continue; }
poi[0] = {1, 1};
if (grid[1][1] < 0) { cout << -1 << endl; continue; }
bool ok = true;
for (int i = 0; i <= K; ++i)
for (int j = 0; j < i; ++j) {
dist[i][j] = dist[j][i] = bfs(i, j);
if (dist[i][j] == -1) ok = false;
}
if (!ok) { cout << -1 << endl; continue; }
int ALL = (1 << (K+1)) - 1;
memset(dp, 0x3f, sizeof(dp));
dp[1][0] = 0;
for (int mask = 0; mask <= ALL; ++mask) {
for (int i = 0; i <= K; ++i) if (dp[mask][i] < INF) {
for (int j = 0; j <= K; ++j) if (!(mask & (1< 經典的「多目標最短路徑」問題，BFS 求點對距離 + 狀態壓縮 DP 解 TSP 變體。注意起點處理與不可達判斷。
