解析：
看了网络上其他人的代码，才明白怎么做。 先用BFS算出，每个点到其他点间的距离，即每个财宝之间的最短路（包括起点），然后状压最短路处理。 具体做法： 状态压缩，1表示当前的财宝已经得到，0表示当前的财宝还未得到。 。 那么枚举下一次要到达的点 j。 得出状态转移公式为：
注意：
有两种情况起点为负数，财宝之间不能联通，这两种情况要输出-1；存在一个财宝且财宝在原点，这种情况要输出0。
AC代码
;ll;const int INF = 0x3f3f3f3f;const int N = 105;const int dx[] = {-1, 0, 1, 0};const int dy[] = { 0,-1, 0, 1};struct Point {int x, y;Point() {}Point(int _x, int _y) {x = _x, y = _y;}}poi[20];struct Node {int x, y, dist;Node() {}Node(int _x, int _y, int _dist) {x = _x; y = _y; dist = _dist;}};int grid[N][N], dist[20][20], dp[(1<<12)][20];int n, m, tot;bool vis[N][N];int bfs(int star, int end) {memset(vis, false, sizeof(vis));queue<Node> que;que.push(Node(poi[star].x, poi[star].y, 0));int step, x, y;while(!que.empty()) {Node front = que.front();que.pop();if(front.x == poi[end].x && front.y == poi[end].y)return front.dist;for(int i = 0; i < 4; i++) {x = front.x + dx[i];y = front.y + dy[i];if(x < 1 || x > n || y < 1 || y > m || grid[x][y] < 0) continue;if(!vis[x][y]) {vis[x][y] = true;step = front.dist + 1;que.push(Node(x, y, step));}}}return -1;}bool getDist() {memset(dist, 0, sizeof(dist));for(int i = 0; i <= tot; i++) {for(int j = 0; j < i; j++) {dist[i][j] = dist[j][i] = bfs(i, j);if(dist[i][j] == -1) return false;}}return true;}int tsp() {memset(dp,INF,sizeof(dp));dp[1][0] = 0;int end = (1<<(tot+1)) – 1;for (int st=0; st <=end; st++)for(int i=0; i <= tot; i++)for(int j=0;j <= tot; j++) {if (i == j) continue;if ((1 << i) & st == 0 || (1 << j) & st == 1) continue;if (dp[st][i] == INF) continue;dp[st|(1<<j)][j]=min(dp[st|(1<<j)][j],dp[st][i]+dist[i][j]);}int ans = INF;for (int i=1;i<=tot;i++)ans=min(ans,dp[end][i]+dist[i][0]);return ans;}int main() {while(scanf(“%d%d”, &n, &m) != EOF) {tot = 0;for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {scanf(“%d”, &grid[i][j]);if(i + j == 2) continue;if(grid[i][j] > 0)poi[++tot] = Point(i, j);}}if(tot == 0) {puts(“0”);continue;}poi[0] = Point(1, 1);if(grid[1][1] < 0 || !getDist()) {puts(“-1”);continue;}printf(“%d\n”, tsp());}return 0;}
，敢于奋斗的人，心中不怕困难。
