题目大意是任意放置两个重力球，可以多次切换重力方向，（上下左右四个方向），问两个重力球相遇的最小重力调整次数。
示例
如上图，若绿圆为重力球的初始位置，则至少调整三次重力方向，可以是两个重力球相遇。该题的难点在于需要查询多次，每次查询重力球的初始位置都会变化，但地图不变。
前置知识该题前置知识主要包括BFS广度优先搜索，多源BFS，最短路
algorithm 1（BFS）单次询问，我们可以使用BFS外加模拟重力球移动来求解，首次相遇时的移动次数即为答案。在多次询问下，如果每次都需要BFS必然会TLE。由于重力球在路过的位置不会停留，实际上我们不必每次都模拟重力球的路线，而是预计算并缓存重力球在某点x上通过改变重力向上、下、左、右可以到达的某点y。即使这样依旧会TLE，我们需要仔细想想其他的方法。
algorithm 2（多源BFS）正难反易，我们逆向考虑一下问题。
对于相遇重力次数改变的问题，A，B两点到O相遇重力改变次数，可从O为起点反向得到。对某一相遇点作为初始node进行BFS遍历，则可计算出任意一对可停留初始点到该相遇点的最少重力改变次数。但是两个重力球的相遇点可能不止一个，所以我们要在二者所有可能的相遇点中，去寻找最少的重力改变次数。如果还是需要多次BFS，那逆向考虑问题好像也没啥作用。
若同时对多个相遇点进行BFS遍历，可将众多相遇点一次性添加到BFS队列中，作为BFS的超级node，再进行BFS，需要边放松操作，用新最优解覆盖原有最优解，并插入新的点对。则可计算出任意一对可停留初始点能够在某点时最少重力切换次数！
可读代码我在代码中关键的位置都加入了注释，包括初始化障碍，生成停留图邻接表，O(1)查询滚动位置，多源DFS等。以下代码参考目前洛谷最佳算法Rainer在此感谢！我做了大量可读性优化，牺牲了部分性能，不过还能挺进TOP3。
代码中一部数组长度为maxn*8，仔细分析，重力球除了初始位置之外，只能停留在四边外围墙内侧一格或障碍物的上下左右四格。对于n*n网络里面有m个障碍物，则重力球停靠的位置不超过4(n m)，若m<=n，则不超过8n。
#include <bits/stdc .h>
using namespace std;
#define ll long long
const int maxn=250 10;
const int dx[]={0,-1,0,1};
const int dy[]={-1,0,1,0};
const int inf=1e8;
int n, m, q, nc=0;
bool block[maxn][maxn];
int node[maxn*8][2], node_id[maxn][maxn], roll[maxn][maxn][4];
vector<int> edge[maxn*8][4];
int dis[maxn*8][maxn*8];/*node_id,node_id,dist*/
int que[maxn*8*maxn*8][2], nq=0;
/*初始化障碍物,外围四边*/
inline void init_block() {
scanf("%d%d%d",&n,&m,&q);
int x,y;
for (int i=1; i<=m; i ) scanf("%d%d",&x,&y), block[x][y]=true;
for (int i=0;i<=n 1;i ) block[0][i] = true;
for (int i=0;i<=n 1;i ) block[n 1][i] = true;
for (int i=0;i<=n 1;i ) block[i][0] = true;
for (int i=0;i<=n 1;i ) block[i][n 1] = true;
}
/*障碍物上下左右创建结点，统计个数，生成id*/
inline void init_node(){
for (int i=1; i<=n; i ) for (int j=1; j<=n; j ) if (!block[i][j]) {
bool flag = false;
for (int k=0; k<4; k ) if (block[i dx[k]][j dy[k]]) flag = true;
if (flag) node[ nc][0]=i, node[nc][1]=j, node_id[i][j]=nc;
}
}
/*生成邻接表*/
inline void init_edge(){
/*利用roll数组缓存，用于后面快速查询滚动位置*/
for (int i=1; i<=n; i ) for (int j=1; j<=n; j ) if (!block[i][j]) {
for (int k=0; k<2; k ) {/*处理上滚，左滚*/
int x=i dx[k], y=j dy[k];
if (!block[x][y]) roll[i][j][k]=roll[x][y][k];
else roll[i][j][k]=node_id[i][j];
if (node_id[i][j]) edge[roll[i][j][k]][k].push_back(node_id[i][j]);
}
}
for (int i=n; i>=1; i--) for (int j=n; j>=1; j--) if (!block[i][j]) {
for (int k=2; k<4; k ) {/*处理下滚，右滚*/
int x=i dx[k], y=j dy[k];
if (!block[x][y]) roll[i][j][k]=roll[x][y][k];
else roll[i][j][k]=node_id[i][j];
if (node_id[i][j]) edge[roll[i][j][k]][k].push_back(node_id[i][j]);
}
}
}
inline void bfs(){
for (int i=1; i<=nc; i ) for (int j=1; j<=nc; j ) dis[i][j]=inf;
for (int i=1; i<=nc; i ) {
dis[i][i]=0;
que[ nq][0]=i; que[nq][1]=i; //队尾插入超级源点（起点id，终点id）;
}
int cur=1;
while (cur<=nq){
int x=que[cur][0], y=que[cur ][1], d=dis[x][y];//队首出列 ，目前为止x,y两点最少次数
for (int i=0; i<4; i )//起初xx，yy相等
for (int xx:edge[x][i])//xx可通过一次i向滚动到x
for (int yy:edge[y][i]){//yy可通过一次i向滚动到y
if (dis[xx][yy]>d 1) {//边放松
printf("pa:(%d,%d)pb:(%d,%d)na(%d,%d)nb(%d,%d)\n",
node[x][0],node[x][1],node[y][0],node[y][1],
node[xx][0],node[xx][1],node[yy][0],node[yy][1]);
dis[xx][yy]=dis[yy][xx]=d 1; //同时更新正反向边更新
que[ nq][0]=min(xx,yy);
que[nq][1]=max(xx,yy);//正向边插入队列,用于更新其他使用该node的dis数据
}
}
}
}
inline void query() {
int ans;
while (q--){
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if (x1==x2&&y1==y2) ans=0;
else {
ans=inf;
for (int i=0; i<4; i ){
int x=roll[x1][y1][i], y=roll[x2][y2][i];//滚动一次，快速查询滚动位置
ans=min(ans, dis[x][y] 1);
}
if (ans>=inf) ans=-1;
}
printf("%d\n", ans);
}
}
int main() {
//freopen("test.in", "r", stdin);
init_block();
init_node();
init_edge();
bfs();
query();
return 0;
}后记
网上没看到太好的题解，索性自己先研究一下，自当备课了。就算是入门组的题想要拿满分也是真心不容易，令人感叹！如果对您有帮助，点个赞吧。不过我内心也清楚，在头条上看这种文章的人很少。
