2018 蓝桥杯省赛 B 组模拟赛（五） F. 结果填空：藏宝图

56 阅读 0 评论 37 点赞

我是靠谱客的博主飘逸大米，最近开发中收集的这篇文章主要介绍2018 蓝桥杯省赛 B 组模拟赛（五） F. 结果填空：藏宝图，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

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

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

跑了1分钟左右。才出来48........

先上第一次代码

#include<iostream>
#include<algorithm>
#include<set>
#include<cmath>
#include<stack>
#include<string>
#include<queue>
#include<vector>
using namespace std;
int fz[4][2]={0,1,1,0,0,-1,-1,0};
int out=99999;
char map[20][20]={"1111111211",
"1110112111",
"1011211011",
"1211101121",
"1011210111",
"1101111011",
"1111101121",
"1010112111",
"1211110011",
"1101102111"};
typedef struct node{
int x;
int y;
}node;
int pd(int x,int y,int v[20][20]){
if(x<0||y<0||x>=10||y>=10||map[x][y]=='0'||v[x][y]==1) return 0;
return 1;
}
int bfs(node n1,node n2,int v[20][20]){
int len[20][20]={0};
queue<node> que;
que.push(n1);
v[n1.x][n1.y]=1;
while(que.size()){
node n1=que.front();
que.pop();
for(int i=0;i<4;i++){
int xx=n1.x+fz[i][0];
int yy=n1.y+fz[i][1];
if(pd(xx,yy,v)){
v[xx][yy]=1;
len[xx][yy]=len[n1.x][n1.y]+1;
if(xx==n2.x&&yy==n2.y) return len[xx][yy];
que.push({xx,yy});
}
}
}
}
int main(){
node no[20];
no[0].x=0,no[0].y=7;
no[1].x=1,no[1].y=6;
no[2].x=2,no[2].y=4;
no[3].x=3,no[3].y=1;
no[4].x=3,no[4].y=8;
no[5].x=4,no[5].y=4;
no[6].x=6,no[6].y=8;
no[7].x=7,no[7].y=6;
no[8].x=8,no[8].y=1;
no[9].x=9,no[9].y=6;
int out=9999;
int a[100]={0,1,2,3,4,5,6,7,8,9};
do{
if(no[a[0]].x>=3&&no[a[0]].y>=3) continue;
int sum=0;
node nn;
nn.x=0,nn.y=0;
int f[20][20]={0};
sum+=bfs(nn,no[a[0]],f);
for(int i=0;i<9;i++){
int v[20][20]={0};
sum+=bfs(no[a[i]],no[a[i+1]],v);
}
int f1[20][20]={0};
sum+=bfs(no[a[9]],nn,f1);
out=min(out,sum);
}while(next_permutation(a,a+10));
cout<<out;
return 0;
}

其实光一个全排列就很长时间了。更别说加上很多最短路径

预处理各个点之间的最短路径。

还是不快，运行了6.7秒左右

#include<iostream>
#include<algorithm>
#include<set>
#include<cmath>
#include<stack>
#include<string>
#include<queue>
#include<vector>
using namespace std;
int fz[4][2]={0,1,1,0,0,-1,-1,0};
int out=99999;
char map[20][20]={"1111111211",
"1110112111",
"1011211011",
"1211101121",
"1011210111",
"1101111011",
"1111101121",
"1010112111",
"1211110011",
"1101102111"};
typedef struct node{
int x;
int y;
}node;
int v[20][20];
int pd(int x,int y){
if(x<0||y<0||x>=10||y>=10||map[x][y]=='0'||v[x][y]==1) return 0;
return 1;
}
int bfs(node n1,node n2){
int len[20][20]={0};
for(int i=0;i<=10;i++){
for(int j=0;j<=10;j++) v[i][j]=0;
}
queue<node> que;
que.push(n1);
v[n1.x][n1.y]=1;
while(que.size()){
node n1=que.front();
que.pop();
for(int i=0;i<4;i++){
int xx=n1.x+fz[i][0];
int yy=n1.y+fz[i][1];
if(pd(xx,yy)){
v[xx][yy]=1;
len[xx][yy]=len[n1.x][n1.y]+1;
if(xx==n2.x&&yy==n2.y) return len[xx][yy];
que.push({xx,yy});
}
}
}
}
int main(){
node no[20];
no[0].x=0,no[0].y=7;
no[1].x=1,no[1].y=6;
no[2].x=2,no[2].y=4;
no[3].x=3,no[3].y=1;
no[4].x=3,no[4].y=8;
no[5].x=4,no[5].y=4;
no[6].x=6,no[6].y=8;
no[7].x=7,no[7].y=6;
no[8].x=8,no[8].y=1;
no[9].x=9,no[9].y=6;
int out=9999;
int llen[20][20]={0};
for(int i=0;i<10;i++){
for(int j=i+1;j<10;j++){
llen[i][j]=bfs(no[i],no[j]);
llen[j][i]=llen[i][j];
}
}
int a[100]={0,1,2,3,4,5,6,7,8,9};
do{
if(no[a[0]].x>=3&&no[a[0]].y>=3) continue;
node nn;
nn.x=0,nn.y=0;
int sum=0;
sum+=bfs(nn,no[a[0]]);
for(int i=0;i<9;i++){
sum+=llen[a[i]][a[i+1]];
}
sum+=no[a[9]].x+no[a[9]].y;
out=min(out,sum);
}while(next_permutation(a,a+10));
cout<<out;
return 0;
}

欢迎大家加入早起学习群，一起学习一起进步！（群号：642179511）