算法总结--广搜4{传送门}

feizhu_QWQ · 2024-07-16 13:54:51 · 算法·理论

如果是这个地图，你必须先传送完后，在传送回来。
因为你唯一的路被堵住了，只能传送完后再传回来，才能走到终点。
所以免费传送门的套路就只有这一个，不要标记传送门！！！！

接着，你需要一个vector储存两个传送门的坐标，可以套一个pair哦！

代码展示：

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[1005][1005];
bool vis[1005][1005];
struct node
{
    int x,y;
}q[1000005];
int head=0,tail=1;
node pre[1005][1005];
bool check(int x,int y)
{
    if(x<1||x>n||y<1||y>m||vis[x][y]==true) return false;
    else return true;
}
void print(int x,int y)
{
    if(x==-1&&y==-1) return;
    print(pre[x][y].x,pre[x][y].y);
    if(x==n&&y==m)
    {
        cout<<n<<" "<<m<<endl;
        exit(0);
    }
    else cout<<x<<" "<<y<<endl;
}
bool work(int x,int y,int sx,int sy)
{
    if(check(x,y)==true)
    {
        head++;
        q[head].x=x;
        q[head].y=y;
        pre[x][y].x=sx;
        pre[x][y].y=sy;
        vis[x][y]=true;
        if(x==n&&y==m) return true;
    }
    return false;
}
void bfs()
{
    head++;
    q[head].x=1;
    q[head].y=1;
    pre[1][1].x=-1;
    pre[1][1].y=-1;
    vis[1][1]=true;
    while(head-tail+1>0)
    {
        int x=q[tail].x;
        int y=q[tail].y;
        tail++;
        if(work(x-1,y,x,y)==true) print(x-1,y);
        if(work(x+1,y,x,y)==true) print(x+1,y);
        if(work(x,y-1,x,y)==true) print(x,y-1);
        if(work(x,y+1,x,y)==true) print(x,y+1);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            if(a[i][j]=='*') vis[i][j]=true;
        }
    }
    bfs();
    return 0;
}

应该不是很难吧！
难的来了！
花费传送门问题
这道题和上一道有三点不同，第一是传送门不止两个互相传送。
第二是传送门需要花费！！
三是不一定必须传送！！

如果是在移动时枚举我们要传送到哪个传送门那里，将会增加很多空间复杂度！！！！
我们做个假设：
我们要从A点传送到B点，再传送到C点，是不是有A+B+B+C，那还不如我们直接从B点传送到C点呢！
所以我们推断出，我们最多使用一次传送门 所以我们可以推出来两种答案：
①不使用传送门
那就普通BFS就行了。
②使用传送门
我们只会使用一次传送，就之用枚举两那个传送门了。
可在极限数据下，这样的优化还是会爆时间复杂度。
我们本来的答案应该是到达离起点最近的传送门要多久 + 离起点最近的传送门的消耗 + 离终点最近的传送门的消耗 + 离终点最近的传送门到终点要多久。
我们把前两者合并为一个，后两者合并为一个，简称dis1,dis2这样方便筛选。

其实我们不用枚举，我们只用找到离起点最近的传送门和离终点最近的传送门就可以了。
我们跑两遍BFS
第一遍以起点为起点，求每个传送门到起点需要走多远
第二遍以终点为起点，求每个传送门到终点需要走多远。
接着把每个传送门到起点/终点要多久加上自己的花费，就有了dis1,dis2
我们把dis1,dis2排个序， 那么第二种答案就是dis1[1] = dis2[1]了！

应该不难吧。
代码较长，等飞竹写完再展示~

今天的传送门结束了！
ヾ(￣▽￣)Bye~Bye~