---

原题链接

题目大意

走迷宫，一个n*m的图，有k个地方毁坏（称为黑洞），有q次询问：问（x1，y1）到（x2，y2）的最小移动次数

思路

显然，暴力跑q边bfs不行！然后就看见42个黑洞点。想着用这42个黑洞点。以这42个黑洞点跑bfs就可以了！但是，下面这个图怎么处理呢？（蓝色部分为黑洞）

答案：特判呗！以u，v作为对顶点的矩形内是否有黑洞，如果没有直接就是曼哈顿距离，否则就以黑洞点跑bfs

注意：在走路的时候不能经过黑洞，所以以黑洞周围的四个点为准跑bfs。

然后就是建图方面！N和M的范围决定了建图有大问题，这里采用new int[] 的方法！

所以，总体解题思路：
属于一道bfs题。分为两点
1、当以起止点作为对顶点所围成的矩形范围内不存在黑洞，最小距离就是曼哈顿距离
2、如果存在黑洞，那么从起始点一定有一条边可以经过黑洞达到终止点。以黑洞四周的四个点维中间点，做bfs找最小距离。
复杂度：O（$164nm$）

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <math.h>
using namespace std;typedef pair<int, int> pii;
const int inf = 0x3f3f3f;int n,m,k,t;
int mov[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};//移动方向int *dist[50][5][200010];//记录距离（需要动态申请空间）
map<pii, int> vis;//标记坐标
set<pii> helo;//记录黑洞的地点void bfs(pii s)
{int idx = vis[s];for(int i = 0 ;i < 4; i++)//便利黑洞周围的四个点{int dx = s.first + mov[i][0];int dy = s.second + mov[i][1];if(dx < 1 || dy < 1 || dx > n || dy > m) continue;//判断越界if(helo.count(make_pair(dx, dy))) continue;//判断是否为黑洞for(int k = 1; k <= n; k++){dist[idx][i][k] = new int[m + 5];//动态申请空间for(int j = 1; j <= m; j++)dist[idx][i][k][j] = inf;}dist[idx][i][dx][dy] = 0;queue<pii> q;//开始走bfsq.push({dx,dy});while(!q.empty()){pii u = q.front();q.pop();for(int j = 0; j < 4; j++)//向四周走{int x = u.first + mov[j][0];int y = u.second + mov[j][1];if(x < 1 || y < 1 || x > n || y > m) continue;if(helo.count(make_pair(x, y))) continue;if(dist[idx][i][x][y] > dist[idx][i][u.first][u.second] + 1){dist[idx][i][x][y] = dist[idx][i][u.first][u.second] + 1;q.push({x,y});}}}}
}bool fid(pii mid, pii u,pii v)//判断黑洞在不在矩形范围内（这里写的很复杂，但是好理解）
{if(u.first >= mid.first && u.second >= mid.second && v.first <= mid.first && v.second <= mid.second) return false;if(u.first <= mid.first && u.second <= mid.second && v.first >= mid.first && v.second >= mid.second) return false;if(u.first >= mid.first && u.second <= mid.second && v.first <= mid.first && v.second >= mid.second) return false;if(u.first <= mid.first && u.second >= mid.second && v.first >= mid.first && v.second <= mid.second) return false;return true;
}
bool jud(pii u, pii v)
{for(auto it = helo.begin(); it != helo.end(); it++){if(!fid((*it), u, v))return false;}return true;
}int main()
{scanf("%d%d%d%d",&n,&m,&k,&t);for(int i = 0; i < k; i++){int x,y;scanf("%d%d",&x,&y);helo.insert({x,y});vis[{x,y}] = i;}for(auto it = helo.begin(); it != helo.end(); it++) bfs(*it);//依次更新每一个黑洞的bfswhile(t--){int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2);pii x = {x1,y1}, y = {x2,y2};if(jud(x,y)){printf("%d\n",(int)(fabs(x1 - x2) + fabs(y1 - y2)));continue;}int ans = inf;for(auto it = helo.begin(); it != helo.end(); it++){int idx = vis[(*it)];for(int i = 0 ;i < 4; i++){int dx = (*it).first + mov[i][0];int dy = (*it).second + mov[i][1];if(dx < 1 || dy < 1 || dx > n || dy > m) continue;if(helo.count(make_pair(dx, dy))) continue;ans = min(ans, dist[idx][i][x1][y1] + dist[idx][i][x2][y2]);}}printf("%d\n",ans == inf ? -1 : ans);}return 0;
}