gym102798 2020CCPC威海B Labyrinth

题目：

给定一个$n\times m$的网格图，图上有$k$个黑洞，从一个点出发一步可以往上下左右走一格，不能走出网格图且不能走进黑洞，给定$q$次询问，每次给定两个点$s,t$，问从$s$到$t$的最少步数，或输出-1表示不能到达。
$(1\le nm\le 200000,0\le k\le 42,1\le q\le 100000)$

题解：

发现黑洞的个数很少，肯定从这里入手。
可以发现如果以$s,t$作为对角顶点的矩形内如果没有黑洞，那么答案为$|s_x-t_x|+|s_y-t_y|$。如果矩形内有黑洞，那么要么不可达，如果可达的话，一定存在一条经过黑洞边上的非黑洞点的路径。所以用$bfs$预处理出所有黑洞边上的非黑洞点到各个点的最短距离，然后每次遍历所有这些点，计算并更新答案。

复杂度：$O(knm+kq)$

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<bitset>
#include<sstream>
#include<ctime>
//#include<chrono>
//#include<random>
//#include<unordered_map>
using namespace std;
#define ll long long
#define ls o<<1
#define rs o<<1|1
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
const double pi=acos(-1.0);
const double eps=1e-6;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const int maxn=2e5+5;
ll read(){
ll x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
queue<pair<pii,int> >q;
int n,m,k,Q;
vector<int>g[maxn],vis[maxn];
pii hole[55];
struct hole_side{
int x,y;
vector<int>dis[maxn];
}hs[205];
int dir[][2]={{1,0},{0,1},{-1,0},{0,-1}};
map<pii,int>buf;
int ck(int x,int y){
return 1<=x&&x<=n&&1<=y&&y<=m;
}
void bfs(hole_side &st){
while(!q.empty())q.pop();
q.push(mp(mp(st.x,st.y),0));
for(int i=1;i<=n;i++){
vis[i].resize(m+1);
fill(all(vis[i]),0);
st.dis[i].resize(m+1);
fill(all(st.dis[i]),-1);
}
vis[st.x][st.y]=1;
while(!q.empty()){
pair<pii,int> u=q.front();q.pop();
st.dis[u.fi.fi][u.fi.se]=u.se;
for(int i=0;i<4;i++){
int nx=u.fi.fi+dir[i][0],ny=u.fi.se+dir[i][1];
if(!ck(nx,ny))continue;
if(vis[nx][ny])continue;
if(g[nx][ny])continue;
vis[nx][ny]=1;
q.push(mp(mp(nx,ny),u.se+1));
}
}
}
int main(void){
// freopen("in.txt","r",stdin);
scanf("%d%d%d%d",&n,&m,&k,&Q);
for(int i=1;i<=n;i++){
g[i].resize(m+1);
fill(all(g[i]),0);
}
int tot=0;
for(int i=1;i<=k;i++){
scanf("%d%d",&hole[i].fi,&hole[i].se);
g[hole[i].fi][hole[i].se]=1;
}
for(int i=1;i<=k;i++){
for(int j=0;j<4;j++){
int nx=hole[i].fi+dir[j][0],ny=hole[i].se+dir[j][1];
if(!ck(nx,ny)||buf[mp(nx,ny)]||g[nx][ny])continue;
++tot;
hs[tot].x=nx;hs[tot].y=ny;
buf[mp(nx,ny)]=1;
}
}
for(int i=1;i<=tot;i++){
bfs(hs[i]);
}
pii s,t;
while(Q--){
scanf("%d%d%d%d",&s.fi,&s.se,&t.fi,&t.se);
if(g[s.fi][s.se]||g[t.fi][t.se]){
puts("-1");
continue;
}
int lx=min(s.fi,t.fi),rx=max(s.fi,t.fi);
int ly=min(s.se,t.se),ry=max(s.se,t.se);
int flag=0;
for(int i=1;i<=tot;i++){
if(lx<=hs[i].x&&hs[i].x<=rx&&ly<=hs[i].y&&hs[i].y<=ry){
flag=1;
break;
}
}
if(!flag){
printf("%dn",rx-lx+ry-ly);
}
else{
int ans=INF;
for(int i=1;i<=tot;i++){
if(hs[i].dis[s.fi][s.se]!=-1&&hs[i].dis[t.fi][t.se]!=-1){
ans=min(ans,hs[i].dis[s.fi][s.se]+hs[i].dis[t.fi][t.se]);
}
}
if(ans==INF)puts("-1");
else{
printf("%dn",ans);
}
}
}
return 0;
}

最后

以上就是无情奇迹为你收集整理的gym102798 2020CCPC威海B Labyrinth的全部内容，希望文章能够帮你解决gym102798 2020CCPC威海B Labyrinth所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。