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

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

1

1 天的时间，蒜头君从入口出发，找到所有宝藏以后，回到出口，最少需要多少天。


算是用暴力吧，先把出口和这10个宝藏从0~10编一下号，然后在建立这11个的最短距离的无向图。；

接着全排列这除了出口的的10个宝藏的先后顺序。这个顺序就是我们寻找宝藏的顺序，接着我们计算这次需要用到的的时间

并更新它就行了

答案是48

代码如下

#include<stdio.h>
#include<algorithm> 
#include<string.h>
#include<queue>

using namespace std;

struct node
{
	int x, y, step;
};

int data[11][11] = {0}; 

int number[11][2];

int disnumber[11][11], map1[11][11], vis[11][11] = {0};

int dir[4][2] = {1,0,0,1,-1,0,0,-1};

void init();

int bfs(int mark)
{
	int x = number[mark][0], y = number[mark][1];
	
	queue <node> que;
	
	node start; start.x = x, start.y = y, start.step = 0;
	
	que.push(start);
	
	memset(vis,0,sizeof(vis));
	
	vis[x][y] = 1;
	
	map1[mark][mark] = 0;
	
	while(!que.empty())
	{
		node now = que.front();
		
		
		if(data[now.x][now.y]==1)
		map1[mark][disnumber[now.x][now.y]] = now.step;
		
		for(int i=0; i < 4; i++)
		{
			int nx = now.x + dir[i][0];
			
			int ny = now.y + dir[i][1];
			
			if(vis[nx][ny] == 0 && nx >=1 && nx <=10 && ny >=1 && ny <= 10 && data[nx][ny] != 2)
			{
				vis[nx][ny] = 1;
				
				node temp ;
				
				temp.x = nx, temp.y = ny, temp.step = now.step + 1;
				
				que.push(temp);
			}
		}
		
		que.pop();
	} 
	
	return 0;
	
}

int main()
{
	init();
	
	for(int i = 1; i <= 10; i++)
	{
		for(int j = 1; j <= 10; j++)
		printf("%d ",data[i][j]);
		printf("\n");
	}
	
	for(int i = 0; i <=10; i++)
	{
		bfs(i);
	}
	
	for(int i = 0; i <= 10; i++)
	{
		for(int j = 0;j <=10; j++)
		printf("%d ",map1[i][j]);
		printf("\n");
	}
	int combination[11];
	for(int i=0;i<=10;i++)
	combination[i]=i;
	int sum  = 9999999;
	int id=0;
	  do 
	  {
	  	int temp_sum=0;
	  	for(int i = 1; i <= 10; i++)
	  	{
	  		temp_sum += map1[combination[i-1]][combination[i]];
	  	}
	  	temp_sum +=map1[combination[10]][0];
	  	if(sum>temp_sum)
	  	{
	  	sum=temp_sum;
	  	} 
	  	
	  }while(next_permutation(combination+1,combination+11));
	  printf("%d\n",sum);
	
	
	
	return 0;
}

void init()
{
	data[1][8]=data[2][7]=data[3][5]=data[4][2]=data[4][9]=data[5][5]=data[7][9]=data[8][7]=data[9][2]=data[10][7]=data[1][1]=1;
	data[2][4]=data[3][2]=data[3][8]=data[4][6]=data[5][2]=data[5][7]=data[6][3]=data[6][8]=data[7][6]=data[8][2]=data[8][4]=data[9][7]=data[9][8]=data[10][3]=data[10][6]=2;
	number[1][0]=1,number[1][1]=8,number[2][0]=2,number[2][1]=7,number[3][0]=3,number[3][1]=5;
	number[4][0]=4,number[4][1]=2,number[5][0]=4,number[5][1]=9,number[6][0]=number[6][1]=5;
	number[7][0]=7,number[7][1]=9,number[8][0]=8,number[8][1]=7,number[9][0]=9,number[9][1]=2,number[0][0]= 1,number[0][1]=1;
	number[10][0]=10,number[10][1]=7;
	
	for(int i=0;i<=10;i++)
	{
		disnumber[number[i][0]][number[i][1]]=i;
	}
}