题目描述
小竹成功从家里逃了出来，他决定去小胖家避一避。但是小胖要求小竹带一个刺激度大于 x 的游戏才能去他家。
为了防止被妈妈或她的朋友发现，小竹不会在道路上行走，而是在建筑物与建筑物之间穿行。
街道表现为一个 n×m 的网格，网格上只有两种建筑: 商店和住宅。商店可以通过而住宅无法通过。
小竹每次从当前所在网格可以行走到上下左右的网格中，但不能移动到网格的边界之外和别人的家中。正式的说，如果他在坐标为 (i,j)的网格里，他可以选择 (i+1,j),(i,j+1),(i−1,j),(i,j−1) , 四个方向行走。
在位置 (i,j)上的商店有一个刺激度为 wi,j的游戏，小竹可以购买他所经过的商店中的游戏并带走。若wi,j 为 −1 则代表这个位置是个住宅，无法通过。
注意：小胖家以及小竹家均可以被通过。
假设相邻的建筑物的距离均为 1，小竹想知道带一个刺激度高于 x 的游戏去小胖家需要的最短距离是多少？如果这是不可能实现的，请输出 −1。
输入描述
第一行三个整数 n,m,x(1≤n,m≤2000,1≤x≤109)
第二行四个整数sx,sy,ex,ey(1≤sx,ex≤n,1≤sy,ey≤m)表示起点与终点的坐标，wsx,sy,wex,ey均为0。
接下来 n 行，每行 m个整数，第 i 行第 j 个整数 wi,j(−1≤wi,j≤109)，其中所有商店的wi,j≥1。
输入：
3 3 1
1 1 3 3
0 1 2
1 1 -1
1 1 0输出：
6
说明：
小竹从家 (1,1) 出发，需要先前往唯一可以购买刺激度大于 1 游戏的商店 ((1,3) 买到刺激度为 2 的游戏再去小胖家。路线为 (1,1)−>(1,2)−>(1,3)−>(1,2)−>(2,2)−>(3,2)−>(3,3)，总距离为6。
解析：可以说双重最短路，先算出起点到每个商店的最短距离，然后可以将每个商店作为新的起点，
注意除了”新起点“之外所有点的距离数组重新初始化为无穷大
，然后最短路算出到终点的距离即可。
#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
const int N=2005;
long long a[N][N];//储存地图
typedef pair<int,int> PII;
vector<PII> v;//来用存商店的坐标
long long dist[N][N],n,m,k,qx,qy,zx,zy,dist2[N][N];
//dist1记录原始起点到各点的最短距离，dist2记录新起点到个点的最短距离
void solve1()//算出dist1
{
memset(dist,0x3f,sizeof dist);
dist[qx][qy]=0;
queue<PII> q;
q.push({qx,qy});
int d1[4]={0,0,1,-1};
int d2[4]={1,-1,0,0};
while(q.size())
{
int x=q.front().first;
int y=q.front().second;
q.pop();
for(int i=0;i<4;i++)
{
int x1=x+d1[i];
int y1=y+d2[i];
if(!(x1>=1&&x1<=n&&y1>=1&&y1<=m)) continue;
if(a[x1][y1]==-1) continue;
if(dist[x1][y1]>dist[x][y]+1)
{
dist[x1][y1]=dist[x][y]+1;
q.push({x1,y1});
}
}
}
}
void solve2()//算出dist2
{
memset(dist2,0x3f,sizeof dist2);
queue<PII> q;
int d1[4]={0,0,1,-1};
int d2[4]={1,-1,0,0};
for(int i=0;i<v.size();i++)
{
int x=v[i].first;
int y=v[i].second;
dist2[x][y]=dist[x][y];//新起点初始距离其实就是原始起点到该点的距离
q.push({x,y});
}
while(q.size())
{
int x=q.front().first;
int y=q.front().second;
q.pop();
for(int i=0;i<4;i++)
{
int x1=x+d1[i];
int y1=y+d2[i];
if(!(x1>=1&&x1<=n&&y1>=1&&y1<=m)) continue;
if(a[x1][y1]==-1) continue;
if(dist2[x1][y1]>dist2[x][y]+1)
{
dist2[x1][y1]=dist2[x][y]+1;
q.push({x1,y1});
}
}
}
if(dist2[zx][zy]>=0x3f3f3f3f) printf("-1\n");
else printf("%lld\n",dist2[zx][zy]);
}
int main()
{
scanf("%lld%lld%lld%lld%lld%lld%lld",&n,&m,&k,&qx,&qy,&zx,&zy);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%lld",&a[i][j]);
if(a[i][j]>k) v.push_back({i,j});
}
}
solve1();
solve2();
return 0;
}