【1】题解：P4442 [COCI 2017/2018 #3] Portal【搜索】【最短路】

· · 题解

最短路。

但是有点难。

我们注意到两个发射位置一定有一个交点。

然后，我们要是在其他点发射，再走一下发射，其实就等同于在交点发射传送门。

所以，我们可以发现：在一个点，射出传送门，一定是比走走再射是更优的。

于是，我们就把问题转化成：

  1. 可走一步。
  2. 可以发射传送门，然后进入一个传送门走到另一个传送门。

这样就可以直接 dijkstra 跑过去了。

接下来我们遇到一个问题：如何计算从一个点发射，到的传送门位置呢？

我们可以使用递推的方式求解。

例如我们计算到左边的墙的距离，可以从 sz_{i,j-1} 转移过来，当这个位置为墙，sz_{i,j}=-1，因为我们要的是到墙旁边的距离，所以一般情况下，sz_{i,j}=sz_{i,j-1}+1。

但是注意到 j-1 可能为 0，同理在右边 j+1 可能为 m+1，所以要对所有边界 sz_{i,j}=-1，不然会出错。

同理，有其他三个方向的转移方程，具体看代码。

然后直接最短路即可。

代码：

代码为了方便，sz 记录的是距离，注意我的循环方向和递推方式，别忘了处理边界。

剩下的看注释。

#include<bits/stdc++.h>
#define int long long
// #define debug
using namespace std;
const int N=500+10;
int n,m,cx,cy,fx,fy,sz[4][N][N],dis[N][N];
bool vis[N][N];
int dx[]={0,0,1,-1}, // L R D U 注意顺序和方向的对应，不然会出问题
    dy[]={-1,1,0,0}; // L R D U
char a[N][N]; // 迷宫
struct srch{ // 当前的搜索状态
    int x,y,d;
    srch(int _x,int _y,int _d){x=_x,y=_y,d=_d;}
};
bool operator<(srch x,srch y){return x.d>y.d;}
priority_queue<srch>q; // dijkstra 的优先队列
signed main(){
    cin>>n>>m;
    for(int i=0;i<=n+1;i++)for(int j=0;j<=m+1;j++)if(i==0||j==0||i==n+1||j==m+1){
        a[i][j]='#'; // 给边界赋初值
        sz[0][i][j]=-1; // 注意到我们计算的是点到墙的距离，那么我们就可以把墙设为 -1，方便递推
        sz[1][i][j]=-1;
        sz[2][i][j]=-1;
        sz[3][i][j]=-1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='C')cx=i,cy=j; // 找起点
            if(a[i][j]=='F')fx=i,fy=j; // 找终点
        }
    }
    // 使用递推的方式求出各个方向到墙的距离
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)sz[0][i][j]=(a[i][j]=='#'?-1:sz[0][i][j-1]+1); // L，从左边转移到墙的距离，注意墙为 -1，那么墙旁边的就会是 0
    for(int i=1;i<=n;i++)for(int j=m;j>=1;j--)sz[1][i][j]=(a[i][j]=='#'?-1:sz[1][i][j+1]+1); // R，同上，从右边转移到墙的距离
    for(int i=n;i>=1;i--)for(int j=1;j<=m;j++)sz[2][i][j]=(a[i][j]=='#'?-1:sz[2][i+1][j]+1); // D，从下边转移到墙的距离
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)sz[3][i][j]=(a[i][j]=='#'?-1:sz[3][i-1][j]+1); // U，从上面转移到墙的距离
    memset(dis,0x3f,sizeof(dis)); // 求最短路
    dis[cx][cy]=0; // 起点
    q.push(srch(cx,cy,0)); // 开始状态
    while(q.size()){ // dijkstra
        srch f=q.top();
        q.pop();
        if(vis[f.x][f.y])continue; // 已经扩展过状态了
        vis[f.x][f.y]=1;
        for(int i=0;i<4;i++){ // 普通移动
            int nx=f.x+dx[i],ny=f.y+dy[i];
            if(nx<1||ny<1||nx>n||ny>m)continue; // 边界
            if(a[nx][ny]=='#')continue; // 障碍物
            if(f.d+1<dis[nx][ny]){ // 更优，选择
                dis[nx][ny]=f.d+1; // 记录答案并计入优先队列
                q.push(srch(nx,ny,f.d+1));
            }
        }
        for(int i=0;i<4;i++){ // Portal 移动
            for(int j=0;j<4;j++)if(i^j){ // 注意方向不能一样
                int nx=f.x+dx[j]*sz[j][f.x][f.y],ny=f.y+dy[j]*sz[j][f.x][f.y]; // 更新位置，这里是先走到 i 方向的传送门，然后转到 j 方向。
                if(nx<1||ny<1||nx>n||ny>m)continue; // 常规最短路的
                if(a[nx][ny]=='#')continue; // 同上
                if(f.d+sz[i][f.x][f.y]+1<dis[nx][ny]){ // 所以，代价是走到 i 传送门的步数加上传送的代价
                    dis[nx][ny]=f.d+sz[i][f.x][f.y]+1; // 更新
                    q.push(srch(nx,ny,dis[nx][ny])); // 再更新
                }
            }
        }
    }
    #ifdef debug // debug 不用管
        for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<dis[i][j]<<" ";}cout<<"\n";}
        for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<sz[0][i][j]<<" ";}cout<<"\n";}
        for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<sz[1][i][j]<<" ";}cout<<"\n";}
        for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<sz[2][i][j]<<" ";}cout<<"\n";}
        for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<sz[3][i][j]<<" ";}cout<<"\n";}
    #endif
    if(dis[fx][fy]==dis[0][0])cout<<"nemoguce\n";
    else cout<<dis[fx][fy]<<"\n"; // 判无解和输出答案
    return 0;
}

注意不要犯弱智错误。