结果填空：藏宝图

藏宝图"/>

结果填空：藏宝图

蒜头君得到一张藏宝图。藏宝图是一个 10×1010 \times 1010×10 的方格地图，图上一共有 101010 个宝藏。有些方格地形太凶险，不能进入。

整个图只有一个地方可以出入，即是入口也是出口。蒜头君是一个贪心的人，他规划要获得所有宝藏以后才从出口离开。

藏宝图上从一个方格到相邻的上下左右的方格需要 111 天的时间，蒜头君从入口出发，找到所有宝藏以后，回到出口，最少需要多少天。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
typedef long long ll;
using namespace std;const int maxn=20;
const int INF=0x3f3f3f3f;
struct Pos{int x,y;Pos(){}Pos(int _x,int _y){x=_x,y=_y;}
}pos[maxn];
/*
输入数据15分钟 
字符更简单 预处理任意两点间的路径，
主要是一个路径的选择，枚举所有的情况，所以用一串
序列来表示 
*/int mp[10][10]={
{0,0,0,0,0,0,0,1,0,0},
{0,0,0,-1,0,0,2,0,0,0},
{0,-1,0,0,3,0,0,-1,0,0},
{0,4,0,0,0,-1,0,0,5,0},
{0,-1,0,0,6,0,-1,0,0,0},
{0,0,-1,0,0,0,0,-1,0,0},
{0,0,0,0,0,-1,0,0,7,0},
{0,-1,0,-1,0,0,8,0,0,0},
{0,9,0,0,0,0,-1,-1,0,0},
{0,0,-1,0,0,-1,10,0,0,0}
};
struct node{int x,y;int sum;
}now,nxt;int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int vis[maxn][maxn];int get_dis(int st,int ed){memset(vis,0,sizeof(vis));queue<node> q;now.x=pos[st].x,now.y=pos[st].y;vis[now.x][now.y]=1;now.sum=0;q.push(now);while(!q.empty()){now=q.front();if(now.x==pos[ed].x&&now.y==pos[ed].y){return now.sum;}q.pop();for(int i=0;i<4;i++){int nx=now.x+dir[i][0],ny=now.y+dir[i][1];if(!vis[nx][ny]&&mp[nx][ny]!=-1){vis[nx][ny]=1;nxt.x=nx,nxt.y=ny,nxt.sum=now.sum+1;q.push(nxt);}}}return INF;
} int dis[maxn][maxn];int rk[10];
int check(){int ans=0;ans+=dis[0][rk[0]];for(int i=1;i<10;i++){ans+=dis[rk[i]][rk[i-1]];}ans+=dis[rk[9]][0];return ans;
}void init(){for(int i=0;i<=10;i++){for(int j=i+1;j<=10;j++){dis[i][j]=dis[j][i]=get_dis(i,j);}}
}int main() {pos[0]=(Pos){0,0};pos[1]=(Pos){0,7};pos[2]=(Pos){1,6};pos[3]=(Pos){2,4};pos[4]=(Pos){3,1};pos[5]=(Pos){3,8};pos[6]=(Pos){4,4};pos[7]=(Pos){6,8};pos[8]=(Pos){7,6};pos[9]=(Pos){8,1};pos[10]=(Pos){9,6};for(int i=0;i<10;i++){rk[i]=i+1;} init();int ans=INF;do{ans=min(ans,check());//printf("***ans:%d\n",ans);}while(next_permutation(rk,rk+10));printf("%d\n",ans);return 0;
}