藏宝图

藏宝图"/>

藏宝图

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

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

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

这道题的思路是，把每个宝藏的坐标标出来，然后将宝藏进行全排列，用广搜找每个宝藏之间的最短距离加上两个路口的距离，然后求出一个距离，只需要找出来所有距离的最小距离就为这道题的最优解

但是，我写了好长时间，到现在都没有跑出来正确答案，有哪位大佬帮我找找bug也是很不错的！（下面第二个是正确答案）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <windows.h>using namespace std;bool book[10][10];
int minn = 99999;
int bz[10][2] = {0,7,1,6,2,4,3,1,3,8,4,4,6,8,7,6,8,1,9,6};//每个宝藏的坐标
int Map[10][10]={//整个地图 2表示不能走 1表示宝藏
{0,0,0,0,0,0,0,1,0,0},
{0,0,0,2,0,0,1,0,0,0},
{0,2,0,0,1,0,0,2,0,0},
{0,1,0,0,0,2,0,0,1,0},
{0,2,0,0,1,0,2,0,0,0},
{0,0,2,0,0,0,0,2,0,0},
{0,0,0,0,0,2,0,0,1,0},
{0,2,0,2,0,0,1,0,0,0},
{0,1,0,0,0,0,2,2,0,0},
{0,0,2,0,0,2,1,0,0,0}
};
struct node
{int x,y,step;
}Now,Next;
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};int bfs(int sx,int sy,int ex,int ey)//用来寻找两个宝藏之间的最短距离
{memset(book,0,sizeof(book));queue<node> q;Now.x = sx;Now.y = sy;book[sx][sy] = true;Now.step = 0;q.push(Now);while(!q.empty()){Now = q.front();q.pop();if(Now.x == ex && Now.y == ey){return Now.step;}for(int i = 0; i < 4; i++){Next.x = dir[i][0] + Now.x;Next.y = dir[i][1] + Now.y;Next.step = Now.step+1;if(Next.x >= 0 && Next.y >=0 && Next.x <= 9 && Next.y <= 9 && Map[Next.x][Next.y] != 2 && book[Next.x][Next.y] == false){book[Next.x][Next.y] = true;q.push(Next);}}}return -1;
}
int res[10];
bool bookres[10];
void dfs(int step)//用来枚举宝藏的寻找顺序
{if(step == 10){int sum = 0;for(int i = 0; i < 10; i++){if(i == 0){sum+=bfs(0,0,bz[res[i]][0],bz[res[i]][1]);}else if(i == 9){sum+=bfs(0,0,bz[res[i]][0],bz[res[i]][1]);}else{sum+=bfs(bz[res[i]][0],bz[res[i]][1],bz[res[i+1]][0],bz[res[i+1]][1]);}}cout << sum ;cout << endl;Sleep(100);minn = min(sum,minn);//cout << minn << endl;return ;}for(int i = 0; i <= 9; i++){if(bookres[i] == false){bookres[i] = true;res[step] = i;dfs(step+1);bookres[i] = false;}}return ;
}int main()
{memset(bookres,0,sizeof(bookres));dfs(0);cout << minn << endl;//cout << bfs(0,0,3,3) << endl;//记住清空bookres标记数组return 0;
}

在我不屑的努力下，终于在电脑跑5分钟的情况下，把答案跑了出来，真是不容易啊

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <windows.h>using namespace std;bool book[10][10];int bz[10][2] = {0,7,1,6,2,4,3,1,3,8,4,4,6,8,7,6,8,1,9,6};//每个宝藏的坐标
int Map[10][10]= //整个地图 2表示不能走 1表示宝藏
{{0,0,0,0,0,0,0,1,0,0},{0,0,0,2,0,0,1,0,0,0},{0,2,0,0,1,0,0,2,0,0},{0,1,0,0,0,2,0,0,1,0},{0,2,0,0,1,0,2,0,0,0},{0,0,2,0,0,0,0,2,0,0},{0,0,0,0,0,2,0,0,1,0},{0,2,0,2,0,0,1,0,0,0},{0,1,0,0,0,0,2,2,0,0},{0,0,2,0,0,2,1,0,0,0}
};
struct node
{int x,y,step;
} Now,Next;int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};int bfs(int sx,int sy, int ex, int ey)
{memset(book,0,sizeof(book));Now.x = sx;Now.y = sy;Now.step = 0;queue<node> q;q.push(Now);book[sx][sy] = true;while(!q.empty()){Now = q.front();q.pop();if(Now.x == ex && Now.y == ey){return Now.step;}for(int i = 0; i < 4; i++){Next.x = Now.x + dir[i][0];Next.y = Now.y + dir[i][1];Next.step = Now.step + 1;if(Next.x >= 0 && Next.x <= 9 && Next.y >= 0 && Next.y <= 9 && Map[Next.x][Next.y] != 2 && book[Next.x][Next.y] == false){book[Next.x][Next.y] = true;q.push(Next);}}}return -1;
}int main()
{int minn = 999999;int num[10] = {0,1,2,3,4,5,6,7,8,9};do{int sum = 0;sum+=bfs(0,0,bz[num[0]][0],bz[num[0]][1]);for(int i = 0; i < 9; i++){sum+=bfs(bz[num[i]][0],bz[num[i]][1],bz[num[i+1]][0],bz[num[i+1]][1]);//cout << sum << " ";}//cout << sum << " ";sum+=bfs(bz[num[9]][0],bz[num[9]][1],0,0);//cout << sum << " "<< endl;minn = min(minn,sum);//Sleep(300);}while(next_permutation(num,num+10));cout << minn << endl;return 0;
}

最后一次代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <windows.h>using namespace std;bool book[10][10];int bz[11][2] = {0,7,1,6,2,4,3,1,3,8,4,4,6,8,7,6,8,1,9,6,0,0};//每个宝藏的坐标
int Map[10][10]= //整个地图 2表示不能走 1表示宝藏
{{0,0,0,0,0,0,0,1,0,0},{0,0,0,2,0,0,1,0,0,0},{0,2,0,0,1,0,0,2,0,0},{0,1,0,0,0,2,0,0,1,0},{0,2,0,0,1,0,2,0,0,0},{0,0,2,0,0,0,0,2,0,0},{0,0,0,0,0,2,0,0,1,0},{0,2,0,2,0,0,1,0,0,0},{0,1,0,0,0,0,2,2,0,0},{0,0,2,0,0,2,1,0,0,0}
};
struct node
{int x,y,step;
} Now,Next;int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};int bfs(int sx,int sy, int ex, int ey)
{memset(book,0,sizeof(book));Now.x = sx;Now.y = sy;Now.step = 0;queue<node> q;q.push(Now);book[sx][sy] = true;while(!q.empty()){Now = q.front();q.pop();if(Now.x == ex && Now.y == ey){return Now.step;}for(int i = 0; i < 4; i++){Next.x = Now.x + dir[i][0];Next.y = Now.y + dir[i][1];Next.step = Now.step + 1;if(Next.x >= 0 && Next.x <= 9 && Next.y >= 0 && Next.y <= 9 && Map[Next.x][Next.y] != 2 && book[Next.x][Next.y] == false){book[Next.x][Next.y] = true;q.push(Next);}}}return -1;
}int main()
{int minn = 999999;int ans[11][11];for(int i = 0; i < 11; i++){for(int j = 0; j < 11; j++){ans[i][j] = bfs(bz[i][0],bz[i][1],bz[j][0],bz[j][1]);}}int num[10] = {0,1,2,3,4,5,6,7,8,9};do{int sum = 0;sum += ans[10][num[0]];for(int i = 0; i < 9; i++){sum += ans[num[i]][num[i+1]];}sum += ans[num[9]][10];minn = min(minn,sum);}while(next_permutation(num,num+10));cout << minn << endl;return 0;
}