广搜(四):传送门问题的进阶运用

DragonL9 · 2024-07-16 16:37:45 · 个人记录

引言：

在广搜(三)中，我们分析了一道传送门问题。那道题中传送门一一配对还免费，而且必须使用。本文将介绍一道升级版的传送门问题。

原题链接：CF1520G To Go Or Not To Go?

阅读题目，我们立刻就能发现本题与前文提到的题目的不同之处。本题每走一步需要花费，使用传送门也有代价，而且传送门可以使用也可以不使用，最后求走到终点的最小代价。类比广搜(三)，我们来分析本题的解题思路。

0	0	0
2	0	0
0	0	4
0	0	0
0	3	0

假设我们要从(2,2)的传送门传送到(5,3)的传送门，如果我们中途经由（3,4）则总花费为2+4+4+3=13,而如果我们直接从(2,2)到(5,3)，花费为2+3=5。由此可见，多次使用传送门不如一次使用传送门，故我们最多只需要一次传送门

接下来，我们来分析最小花费的算法。分两种情况。

情况1：全程不使用传送门

这种情况比较简单，因为花费与步数成正比，我们只需要从起点到终点跑一遍bfs，记录下跑到每一个点的花费即可。

情况2：使用了传送门

这一类情况的解决思路与动态规划有一定的相似之处。我们可以将路程分为以下几个阶段：

A：起点->传送门1;B:传送门1->传送门2;C:传送门2->终点

整体的答案就等于A段花费+B段花费+C段花费

由于我们有多个传送门，且每一个都可能作为传送门1或者传送门2，因此我们需要遍历每一个传送门，分别求出它们到起点和终点的距离，最后选择花费最小的即可。

具体如何操作呢？我们可以使用两个数组dis1和dis2分别存储每个点到起点和终点的距离(此时还不用考虑传送门的价值)。这就意味着我们需要分别从起点和终点开始各跑一遍bfs。接下来，我们用两个数组d1和d2分别记录每一个传送门到起点和终点的花费(此时需要加上当前传送门的花费)，即对于位于(x,y)的编号为i的传送门，d1[i]=dis1[i][j]+a[i][j];d2[i]=dis2[i][j]+a[i][j]。最后，我们令答案ans取不走传送门和走传送门的花费的最小值。在此之前，我们将ans的值初始化为1e18，当我们计算完成后如果ans的值还是1e18(大于1e17即可)，则说明不可能到达，就输出-1。否则输出ans的值

最后，代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e3+7;
int a[N][N];
int w,n,m; 
ll dis1[N][N];//dis1[x][y]表示从起点出发到(x,y)的最小花费，不考虑传送门 
ll dis2[N][N];//dis2[x][y]表示从终点出发到(x,y)的最小花费，不考虑传送门
ll d1[N*N];//表示传送门(i,j)+dis1[i][j]的花费
ll d2[N*N];//表示传送门(i,j)+dis2[i][j]的花费 
//传送门最多用1次 
bool vis[N][N];
struct node{
    int x,y,step; 
};
queue<node>q;//传入的队列 
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
void init(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            vis[i][j]=0;
        }
    }
    return;
}
bool check(int x,int y){
    return x>=1&&x<=n&&y>=1&&y<=m&&!vis[x][y]&&a[x][y]!=-1;
}
void bfs(int x,int y,int op){//op==0从起点出发,op==1从终点出发 
    init();
    while(!q.empty()) q.pop();
    q.push({x,y,0});
    vis[x][y]=1;//标记起点
    if(op==0){
        dis1[x][y]=0;
    }
    if(op==1){
        dis2[x][y]=0;
    }
    while(!q.empty()){
        node u=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int xx=u.x+dx[i];
            int yy=u.y+dy[i];
            if(check(xx,yy)){
                if(op==0){
                    dis1[xx][yy]=dis1[u.x][u.y]+w;
                }
                if(op==1){
                    dis2[xx][yy]=dis2[u.x][u.y]+w;
                }
                vis[xx][yy]=1;
                q.push({xx,yy,u.step+1});
            }
        }
    }
} 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>w;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dis1[i][j]=dis2[i][j]=-1;
        }
    }
    bfs(1,1,0);//从起点出发 
    bfs(n,m,1);//从终点出发
    ll ans=1e18;//直接到达 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]>=0&&dis1[i][j]>=0&&dis2[i][j]>=0){
                ans=min(ans,dis1[i][j]+dis2[i][j]);
            }

        }
    }
    int len1=0,len2=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]>0&&dis1[i][j]>=0){
                //记录起点到传送门,直接传送->? 
                d1[++len1]=a[i][j]+dis1[i][j];

            }
            if(a[i][j]>0&&dis2[i][j]>=0){
                //记录起点到传送门,直接传送->? 
                d2[++len2]=a[i][j]+dis2[i][j];

            }
        }
    }
    sort(d1+1,d1+1+len1);
    sort(d2+1,d2+1+len2);

    if(len1&&len2)ans=min(d1[1]+d2[1],ans);
    if(ans>1e17){
        cout<<-1;
        return 0;
    } 
    cout<<ans;
    return 0;
}

结语:

以上就是本题的全部内容。本题有难度，主要难点在于需要考虑是否使用传送门的情况，还需要谨慎判断无解的情况。同时本题代码较长，细节很多，需要仔细检查，避免出错。