题意

题目链接

给出一个正方形区域，其中有一些点是障碍。每次询问给出两个球的初始位置，询问至少需要改变几次重力才能使两球相遇。

解析

首先我们发现，实际上仅有障碍周围（包括地图边界）上的点是有意义的（因为任何位置的球经过一次操作一定会到这些点，显然一次操作是可以枚举的）。我们定义每一组有意义的 $(x,y)$ 为一个状态，显然最多状态数为 $2000$ 左右，而两个球的状态种数就为 $4\times {10}^6$，是可以接受的。

我们可以考虑先将所有有意义的点对 $(x,y)$ 都进行编号，作为这个点的状态号。然后我们预处理出从每一点进行某一方向的操作后所到达的状态数。这部分代码如下：

inline bool check(int i,int j){
    if(a[i-1][j]||a[i+1][j]||a[i][j-1]||a[i][j+1]) return true;
    return false;
}
……
scanf("%d%d%d",&n,&m,&Q);
for(int i=1,x,y;i<=m;i++){
    scanf("%d%d",&x,&y);
    a[x][y]=1;//标记障碍
}
for(int i=1;i<=n;i++) a[0][i]=a[n+1][i]=a[i][0]=a[i][n+1]=1;//标记障碍
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        if(!a[i][j]&&check(i,j)) id[i][j]=++tot;//对有意义的点进行编号
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) 
        t[i][j][0]=a[i][j-1]?id[i][j]:t[i][j-1][0],
        t[i][j][1]=a[i-1][j]?id[i][j]:t[i-1][j][1];
for(int i=n;i;i--)
    for(int j=n;j;j--)
        t[i][j][2]=a[i][j+1]?id[i][j]:t[i][j+1][2],
        t[i][j][3]=a[i+1][j]?id[i][j]:t[i+1][j][3];
        //分别处理出从 (i,j) 向各个方向走所到达的点的状态号

				

					
				
				

					
				
				

					
				
				

					
				
			

接着我们发现两个小球最终相遇，相当于是两个球所在的点编号相同了，因此我们可以考虑从终点开始逆推。那么怎么转移状态呢？我们可以将每一个状态看作一个点，如果状态 $i$ 可以转移到状态 $j$，我们就从 $j$ 向 $i$ 连一条边（因为后边要逆推，所以建反边）。同样的，我们只需要在有意义的点之间连边就可以了。这部分代码如下：

inline void add(int u,int v,int p){
    e[++cnt].to=v;
    e[cnt].nxt=head[u][p];
    head[u][p]=cnt;//每个点的四种状态都需要一个 head，因为转移时需要枚举方向
}
……
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        if(id[i][j]) for(int k=0;k<=3;k++) add(t[i][j][k],id[i][j],k);//建反边

				

					
				
				

					
				
				

					
				
				

					
				
			

接着，我们定义 $di{s}_{i,j}$ 为状态为 $i,j$ 的两个小球所想要相遇所需要的操作数。定义 $di{s}_{i,i}=1$（因为到时候要消耗一步来枚举第一步，干脆直接把初值赋值为 $1$，然后特判相等的情况更为方便）。然后我们在这张图上进行 bfs，每次枚举 $i,j$ 两个状态分别所能到达的其他状态并更新所到达的这两个状态间的距离。由于两个球的状态种数仅为 $4\times {10}^6$，且每一个状态至多创造 $4$ 条边，所以 bfs 的复杂度是可接受的。这部分代码如下：

queue<pair<int,int> > q;
for(int i=1;i<=tot;i++)
    for(int j=1;j<=tot;j++)
        dis[i][j]=1e9+7;
for(int i=1;i<=tot;i++) q.push(make_pair(i,i)),dis[i][i]=1;//赋初值并 push 进队列
while(!q.empty()){
    pair<int,int> x=q.front();q.pop();
    for(int k=0;k<=3;k++){//枚举方向
        for(int i=head[x.first][k];i;i=e[i].nxt){
            for(int j=head[x.second][k];j;j=e[j].nxt){//枚举到达的状态
                int u=e[i].to,v=e[j].to;
                if(dis[u][v]==1e9+7){
                    dis[u][v]=dis[x.first][x.second]+1,
                    q.push(make_pair(u,v));//更新并 push 进队列
                }
            }
        }
    }
}

				

					
				
				

					
				
				

					
				
				

					
				
			

最后对于每一次询问，如果两个点重合输出 $0$，否则枚举两个球一步操作后的状态并取最小值，如果这个结果过大的话说明这两个状态间没有通路，输出 $-1$，否则输出这个结果。这部分代码如下：

inline int getans(int X1,int Y1,int X2,int Y2){
    return min(dis[t[X1][Y1][0]][t[X2][Y2][0]],min(dis[t[X1][Y1][1]][t[X2][Y2][1]],min(dis[t[X1][Y1][2]][t[X2][Y2][2]],dis[t[X1][Y1][3]][t[X2][Y2][3]])));
}
……
for(int i=1,X1,X2,Y1,Y2;i<=Q;i++){
    scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
    if(X1==X2&&Y1==Y2) printf("0\n");//重合
    else{
        int ans=getans(X1,Y1,X2,Y2);
        if(ans>=1e9) printf("-1\n");//无解
        else printf("%d\n",ans);//有解
    }
}

				

					
				
				

					
				
				

					
				
				

					
				
			

至此，这道题就被我们解决了。化点为状态，以及在状态之间进行连边以便于转移的操作非常巧妙，值得思考。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=305,M=2005,MN=1e5+5;
struct edge{
    int to,nxt;
}e[MN];
int a[N][N],dis[M][M],id[N][N],t[M][M][4];
int n,m,Q,cnt,head[M][4],tot;
inline void add(int u,int v,int p){
    e[++cnt].to=v;
    e[cnt].nxt=head[u][p];
    head[u][p]=cnt;
}
inline bool check(int i,int j){
    if(a[i-1][j]||a[i+1][j]||a[i][j-1]||a[i][j+1]) return true;
    return false;
}
inline int getans(int X1,int Y1,int X2,int Y2){
    return min(dis[t[X1][Y1][0]][t[X2][Y2][0]],min(dis[t[X1][Y1][1]][t[X2][Y2][1]],min(dis[t[X1][Y1][2]][t[X2][Y2][2]],dis[t[X1][Y1][3]][t[X2][Y2][3]])));
}
queue<pair<int,int> > q;
int main(){
    scanf("%d%d%d",&n,&m,&Q);
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        a[x][y]=1;
    }
    for(int i=1;i<=n;i++) a[0][i]=a[n+1][i]=a[i][0]=a[i][n+1]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(!a[i][j]&&check(i,j)) id[i][j]=++tot;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) 
            t[i][j][0]=a[i][j-1]?id[i][j]:t[i][j-1][0],
            t[i][j][1]=a[i-1][j]?id[i][j]:t[i-1][j][1];
    for(int i=n;i;i--)
        for(int j=n;j;j--)
            t[i][j][2]=a[i][j+1]?id[i][j]:t[i][j+1][2],
            t[i][j][3]=a[i+1][j]?id[i][j]:t[i+1][j][3];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(id[i][j]) for(int k=0;k<=3;k++) add(t[i][j][k],id[i][j],k);
    for(int i=1;i<=tot;i++)
        for(int j=1;j<=tot;j++)
            dis[i][j]=1e9+7;
    for(int i=1;i<=tot;i++) q.push(make_pair(i,i)),dis[i][i]=1;
    while(!q.empty()){
        pair<int,int> x=q.front();q.pop();
        for(int k=0;k<=3;k++){
            for(int i=head[x.first][k];i;i=e[i].nxt){
                for(int j=head[x.second][k];j;j=e[j].nxt){
                    int u=e[i].to,v=e[j].to;
                    if(dis[u][v]==1e9+7){
                        dis[u][v]=dis[x.first][x.second]+1,
                        q.push(make_pair(u,v));
                    }
                }
            }
        }
    }
    for(int i=1,X1,X2,Y1,Y2;i<=Q;i++){
        scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
        if(X1==X2&&Y1==Y2) printf("0\n");
        else{
            int ans=getans(X1,Y1,X2,Y2);
            if(ans>=1e9) printf("-1\n");
            else printf("%d\n",ans);
        }
    }
    return 0;
}