https://ac.nowcoder.com/acm/contest/45670/D
- 题目描述：
小竹成功从家里逃了出来，他决定去小胖家避一避。但是小胖要求小竹带一个刺激度大于 xx 的游戏才能去他家。
为了防止被妈妈或她的朋友发现，小竹不会在道路上行走，而是在建筑物与建筑物之间穿行。
街道表现为一个n×m 的网格，网格上只有两种建筑: 商店和住宅。商店可以通过而住宅无法通过。
小竹每次从当前所在网格可以行走到上下左右的网格中，但不能移动到网格的边界之外和别人的家中。正式的说，如果他在坐标为 (i,j)的网格里，他可以选择 (i+1,j) , (i,j+1) , (i - 1,j) , (i,j-1)四个方向行走。
在位置 (i,j)(i,j) 上的商店有一个刺激度为 w{i,j}的游戏，小竹可以购买他所经过的商店中的游戏并带走。若 w{i,j} 为 -1 则代表这个位置是个住宅，无法通过。
注意：小胖家以及小竹家均可以被通过。
假设相邻的建筑物的距离均为 1，小竹想知道带一个刺激度高于 x 的游戏去小胖家需要的最短距离是多少？如果这是不可能实现的，请输出 −1。 - 题目分析：意思是要在通过至少一个刺激度高于x的商店的前提下，求起点到终点的最短路。单源最短路无法解决这个问题。
- 解法一：从起点和终点分别进行一遍bfs，双向搜索，维护两点到图上任一点的最短路径，最后枚举刺激度高于x的商店，取最小值
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int mp[2010][2010];
int n,m,x;
int sx,sy,ex,ey;
int vis[2010][2010] = {0};
int dis1[2010][2010];
int dis2[2010][2010];
struct ty{
int x;
int y;
int step;
};
queue<ty> q;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int main(){
cin>>n>>m>>x;
cin>>sx>>sy>>ex>>ey;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
cin>>mp[i][j];
}
}
memset(dis1,0x3f3f3f3f,sizeof(dis1));
memset(dis2,0x3f3f3f3f,sizeof(dis1));
memset(vis,0,sizeof(vis));
q.push({sx,sy,0});
vis[sx][sy] = 1;
while(!q.empty()){
ty op = q.front();
q.pop();
for(int i = 0 ;i<=3;i++){
int nx = op.x+dx[i];
int ny = op.y + dy[i];
if(nx<1||nx>n||ny<1||ny>m||vis[nx][ny]||mp[nx][ny]==-1) continue;
q.push({nx,ny,op.step+1});
dis1[nx][ny] = op.step+1;
vis[nx][ny] = 1;
}
}
while(!q.empty()) q.pop();
memset(vis,0,sizeof(vis));
q.push({ex,ey,0});
vis[ex][ey] = 1;
while(!q.empty()){
ty op = q.front();
q.pop();
for(int i = 0 ;i<=3;i++){
int nx = op.x+dx[i];
int ny = op.y + dy[i];
if(nx<1||nx>n||ny<1||ny>m||vis[nx][ny]||mp[nx][ny]==-1) continue;
q.push({nx,ny,op.step+1});
dis2[nx][ny] = op.step+1;
vis[nx][ny] = 1;
}
}
int ans = 0x3f3f3f3f;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
if(mp[i][j]>x){
ans = min(dis1[i][j]+dis2[i][j],ans);
}
}
}
if(ans==0x3f3f3f3f) cout<<-1<<endl;
else
cout<<ans<<endl;
}
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int mp[2010][2010][2];
int n,m,x;
int sx,sy,ex,ey;
int vis[2010][2010][2] = {0};
struct ty{
int x;
int y;
int z;
int step;
};
deque<ty> q;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int bfs(){
memset(vis,0,sizeof(vis));
q.push_back({sx,sy,0,0});
while(!q.empty()){
ty op = q.front();
q.pop_front();
if(vis[op.x][op.y][op.z]) continue;//访问过的点跳过
vis[op.x][op.y][op.z] = 1;
if(op.z<1&&mp[op.x][op.y][op.z]>x){
q.push_front({op.x,op.y,op.z+1,op.step});
}//通过关键点走向上一层
if(op.x==ex&&op.y==ey&&op.z==1) return op.step;
for(int i = 0 ;i<=3;i++){
int nx = op.x+dx[i];
int ny = op.y + dy[i];
if(nx<1||nx>n||ny<1||ny>m||vis[nx][ny][op.z]||mp[nx][ny][op.z]==-1) continue;
q.push_back({nx,ny,op.z,op.step+1});
}
}
return -1;
}
int main(){
cin>>n>>m>>x;
cin>>sx>>sy>>ex>>ey;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
cin>>mp[i][j][0];
mp[i][j][1] = mp[i][j][0];
}
}
cout<<bfs()<<endl;
}