藏宝图（蓝桥杯模拟5）

56 阅读 0 评论 37 点赞

我是靠谱客的博主可爱黑夜，最近开发中收集的这篇文章主要介绍藏宝图（蓝桥杯模拟5），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

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

藏宝图上从一个方格到相邻的上下左右的方格需要

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

解析：

思路：

先通过bfs求出宝藏之间的距离（把出入口也看成宝藏，用1表示宝藏的位置，在数组中就是1与1的距离），

然后通过dfs求出最短路径。

细节：

1，为了方便求1与1之间的距离，所以把等于1的点存入一个数组v，1与1的距离用e[][]数组来存；

2，bfs用了优先队列；

3，dfs别忘了还要从入口出去。

当然这样时间复杂度过高也无所谓，谁要这是蓝桥被呢。

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
int inf=0x3f3f3f3f;
char mapp[11][11]=
{
"1......1..",
"...*..1...",
".*..1..*..",
".1...*..1.",
".*..1.*...",
"..*....*..",
".....*..1.",
".*.*..1...",
".1....**..",
"..*..*1..."
};
struct node
{
int x,y;
int s;
bool friend operator <(node a,node b)
{
return a.s>b.s;
}
} p;
vector<node>v;
int e[11][11];
void init()
{
for (int i=0; i<10; i++)
for (int j=0; j<10; j++)
if(mapp[i][j]=='1')
{
p.x=i;
p.y=j;
v.push_back(p);
}
fill(e[0],e[0]+10*11,inf);
}
int sx,sy,ex,ey;
int to[4][2]= {1,0,0,1,-1,0,0,-1};
int vis[11][11];
int bfs(int x,int y)
{
priority_queue<node>q;
memset(vis,0,sizeof(vis));
p.x=x,p.y=y,p.s=0;
q.push(p);
vis[x][y]=1;
while(!q.empty())
{
p=q.top();
q.pop();
if(p.x==ex&&p.y==ey)
{
return p.s;
}
node nx;
for (int i=0; i<4; i++)
{
nx.x=p.x+to[i][0];
nx.y=p.y+to[i][1];
if(nx.x<0||nx.x>=10||nx.y<0||nx.y>=10||mapp[nx.x][nx.y]=='*'||vis[nx.x][nx.y])
continue;
vis[nx.x][nx.y]=1;
nx.s=p.s+1;
q.push(nx);
}
}
return 0;
}
int summin=inf,len,f[11];
int trace[11];
int endtrace[11];
void dfs(int id,int step,int sum)
{
trace[step]=id;
if(step==len-1)
{
if(sum+e[id][0]<summin)
{
for (int i=0;i<len;i++)
endtrace[i]=trace[i];
summin=sum+e[id][0];
}
return ;
}
f[id]=1;
for (int i=0; i<len; i++)
if(!f[i]&&e[id][i]!=inf)
dfs(i,step+1,sum+e[id][i]);
f[id]=0;
}
int main ()
{
init();
len=v.size();
for (int i=0; i<len; i++)
for (int j=0; j<=i; j++)
if(i!=j)
{
sx=v[i].x,sy=v[i].y;
ex=v[j].x,ey=v[j].y;
int d=bfs(sx,sy);
e[i][j]=d;
e[j][i]=d;
}
dfs(0,0,0);
cout<<summin<<endl;
for (int i=0;i<len;i++)
cout<<endtrace[i]<<"->";
cout<<0;
return 0;
}