題目大意:給出一個 n * m 的矩陣,在矩陣內部最有 k 個黑洞(表示不可行走的區域),現在給出 q 次詢問,每次詢問給出兩個點 ( x1 , y1 ) 和 ( x2 , y2 ) ,問從點 ( x1 , y1 ) 到點 ( x2 , y2 ) 的最短路是多少
題目分析:本題一個很重要的思維點:
又因為黑洞的數量很小,所以可以用 bfs 預處理,然後對於每個查詢來說直接列舉中間點維護最短距離就好了,預處理的時間複雜度是 O( n * m * k ),查詢的時間複雜度是 O( q * k ),我在預處理時還套了一個 set 用來判斷是否為黑洞點,所以還需要加個 log,不過無傷大雅
然後有個坑點就是這個題不能用 vector 來儲存矩陣,會 MLE,換成 C++ 的 new 動態開記憶體就能過了
程式碼:
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const int N=2e5+100;
const int b[4][2]={0,1,0,-1,1,0,-1,0};
int n,m,k,q;
set<pair<int,int>>st;
int* dis[50][4][N];//dis[black_hole_id][pos][x][y]
vector<pair<int,int>>node;
struct Node
{
int x,y,step;
Node(){}
Node(int x,int y,int step):x(x),y(y),step(step){}
};
void bfs()
{
for(int id=0;id<node.size();id++)//列舉黑洞
{
int x,y;
tie(x,y)=node[id];
for(int pos=0;pos<4;pos++)//列舉四周的每個位置
{
int xx=x+b[pos][0];
int yy=y+b[pos][1];
if(xx<=0||yy<=0||xx>n||yy>m)//起點越界
continue;
for(int i=1;i<=n;i++)
{
dis[id][pos][i]=new int[m+5];
for(int j=1;j<=m;j++)
dis[id][pos][i][j]=inf;
}
if(st.count(make_pair(xx,yy)))//起點是黑洞
continue;
queue<Node>q;
dis[id][pos][xx][yy]=0;
q.push(Node(xx,yy,0));
while(q.size())
{
Node cur=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int xx=cur.x+b[i][0];
int yy=cur.y+b[i][1];
if(xx<=0||yy<=0||xx>n||yy>m)
continue;
if(dis[id][pos][xx][yy]!=inf)//已經遍歷過了
continue;
if(st.count(make_pair(xx,yy)))//黑洞
continue;
dis[id][pos][xx][yy]=cur.step+1;
q.push(Node(xx,yy,cur.step+1));
}
}
}
}
}
bool check(int x1,int y1,int x2,int y2)//檢查[x1,x2]X[y1,y2]內是否有黑洞
{
if(x1>x2)
swap(x1,x2);
if(y1>y2)
swap(y1,y2);
for(int i=0;i<k;i++)
{
int x,y;
tie(x,y)=node[i];
if(x1<=x&&x<=x2&&y1<=y&&y<=y2)
return true;
}
return false;
}
int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);
scanf("%d%d%d%d",&n,&m,&k,&q);
for(int i=1;i<=k;i++)
{
int x,y;
scanf("%d%d",&x,&y);
st.emplace(x,y);
node.emplace_back(x,y);
}
bfs();
while(q--)
{
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(!check(x1,y1,x2,y2))//內部沒有黑洞
printf("%d\n",abs(x1-x2)+abs(y1-y2));
else
{
int ans=inf;
for(int i=0;i<k;i++)
for(int pos=0;pos<4;pos++)
{
int xx=node[i].first+b[pos][0];
int yy=node[i].second+b[pos][1];
if(xx<=0||yy<=0||xx>n||yy>m)
continue;
ans=min(ans,dis[i][pos][x1][y1]+dis[i][pos][x2][y2]);
}
if(ans==inf)
ans=-1;
printf("%d\n",ans);
}
}
return 0;
}