题解：CF1301F Super Jaber

DragonL9 · 2024-07-17 22:19:45 · 题解

CF1301F Super Jaber

读完题目后发现，本题没有障碍物，而且每个点都有传送的件，也可以不传送，是典型的非必须分类传送门问题。但是大家别急着做，先把题目读完。读到后面，我们发现：

下一行包含一个整数q(1\le q \le 10^5)，代表任务数

这就是本题的难点所在：有多组询问。

对此，我们最容易想到的解法是对每一次询问都跑一遍bfs，但是，毫无疑问，这种做法保证TLE。此时，我们可以考虑将图上所有点之间的最短距离预处理出来。

如何实现这一点呢？在CF1520G中，我们在处理使用传送门的情况时，将全程分为了起点->传送门1->传送门2->终点这几个阶段。类比这一思路，我们可以将本题的全程分为起点->传送门->终点这几个阶段。由于本题可以使用多种和多个传送门，我们需要将每一种颜色中的所有传送门到其它任意点的最短距离。此时我们需要引入多源bfs，即广搜的起点有多个。实现的方式也很简单：在开始时将所有的该种传送门加入队列，可以形成如下图的效果：其中门为传送门，数字为当前点到最近的该类传送门的步数

由此，对于这类传送门，我们所求的答案就是:

起点到最近传送门的距离+终点到最近传送门的距离+1

那么如果我们在求解当前颜色的时候要使用其它颜色(之前没有使用过该颜色)的传送门呢？(即多种颜色的传送门混用) 此时，每当我们到了一个点想使用其他颜色的传送门时，便以该点为起点尝试着传送到这个点能传送到的所有点。每当我们传送到了点之后，判断该点使用新颜色传送是否比使用旧颜色传送更优。如果更优就更新为新颜色，否则不变。

例如，我们假设从上表中的(1,4)可以利用另一种颜色的传送门直接传送到(1,1)，那么我们判断：使用新颜色的花费为1+1=2，使用旧颜色的花费为3，则使用新颜色更优。

注意：使用新颜色进行更新是在目标点被旧颜色走过的基础上进行的。如果目标点没有走过则该操作无意义，可以等到统一搜索新颜色时再进行。

由上，我们可以得出任意点之间的最短距离。最后，每当我们处理一次询问时，将答案ans存储为两点之间的曼哈顿距离。接着，我们遍历每一种颜色，让ans取每种颜色下这两点之间距离的最小值。(注意：每一种下可能包含颜色混用)

更多细节详见代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+100;
int a[N][N];
bool vis[N][N];
int dis[45][N][N];//dis[k][i][j]表示到达(i,j)通过k传送最短的时间 
//必须指定最终的传送门 
bool flag[42];
struct tp{
    int x,y;
};
vector<tp>G[45];
int n,m,k;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
struct node{
    int x,y,step;
};

bool check(int x,int y){
    return x>=1&&x<=n&&y>=1&&y<=m&&!vis[x][y];
}
void bfs(int num){//num表示颜色 
    memset(vis,0,sizeof vis);
    queue<node>q;
    for(int i=0;i<G[num].size();i++){//多源bfs,起点全部入队 
        int x=G[num][i].x;
        int y=G[num][i].y;
        dis[num][x][y]=0;
        q.push({x,y,0});
        vis[x][y]=1;
    }
    memset(flag,0,sizeof flag);//判断混用的新颜色是否已考虑过 
    while(!q.empty()){
        node u=q.front();
        q.pop();
        int x=u.x,y=u.y;
        for(int i=0;i<4;i++){
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(check(xx,yy)){
                if(dis[num][xx][yy]>dis[num][x][y]+1){//更优的传送门 
                    dis[num][xx][yy]=dis[num][x][y]+1;
                    q.push({xx,yy,u.step+1});
                }
            }
        }
        if(flag[a[x][y]]==0){//使用其他颜色的传送门 
            flag[a[x][y]]=1;
            for(int i=0;i<G[a[x][y]].size();i++){
                int xx=G[a[x][y]][i].x;
                int yy=G[a[x][y]][i].y;
                if(vis[xx][yy]==0){//注意，此处的vis不是普通广搜的vis，是用来标记这个点是否作为新颜色考虑过 
                    if(dis[num][xx][yy]>dis[num][x][y]+1){//使用后更优才更新 
                        vis[xx][yy]=1;
                        q.push({xx,yy,u.step+1});
                        dis[num][xx][yy]=dis[num][x][y]+1;
                    }
                }
            }
        }
    }
    return ;
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            G[a[i][j]].push_back({i,j});//存储对应颜色的传送门的坐标 
        }
    }
    memset(dis,0x3f,sizeof dis);//一开始所有距离都是初始值最大
    for(int i=1;i<=k;i++){
        bfs(i);
    }
    int q;
    cin>>q;
    while(q--){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        int ans=abs(x1-x2)+abs(y1-y2);//曼哈顿距离 
        for(int i=1;i<=k;i++){//遍历每种颜色 
            ans=min(ans,dis[i][x1][y1]+dis[i][x2][y2]+1);
        }
        cout<<ans<<endl;
    }
    return 0;
}