题解 | #迷宫2#

思路

题意：求 让蜥蜴没办法达到终点所必须花费的最小总代价
我们通过 把特殊的走道转化为墙壁（ 转换代价为g[i][j] ），来使蜥蜴最终无法到达终点

g[i][j]取不同值的意义：-1代表墙壁，0代表走道，而1到10^9之间的正整数代表特殊的走道。
因为 g[i][j] = -1 代表已经是墙壁，故转换代价为 0，因此我们让 g[i][j] = -1的，g[i][j] = 0
而g[i][j] = 0 的 代表无法转换为墙壁，故代价是无穷大，因此我们让 g[i][j] = 0的，g[i][j] = 1e18

因为 蜥蜴在左上角，终点在右下角，要使得蜥蜴无法到达终点 就必须 有 ''一道墙'' 把蜥蜴或者终点给围起来

围墙的位置 有以下四种情况：

到这里，问题便转换为了 建造一面最小花费的围墙，围墙的情况或格式只有四种 ：见上面图片

我们用 堆优化dijkstra 来解决问题：

① 所有可能的起点入队 ，起点：围墙的头部 
在这里我们规定 头部要么在上端，要么在右端，则尾部 要么在下端，要么在左端

② 弹出最小花费的点 ，用该点更新 到其后继点的最小花费
若弹出的点 可能作为围墙尾部（在左端或者在下端），用到该点的最小花费，来更新最终答案

③ 后继点入队

综上，Code 如下 .

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 510;

typedef long long ll;

struct node{
    int x,y;
    ll w;
    bool operator < (const node &x) const{
        return w > x.w;
    }
};
int rou[4][2]={-1,0,0,1,1,0,0,-1};
bool st[N][N];
ll g[N][N];
int T,n,m;

int main(){
    cin>>T>>n>>m;

    while(T--){
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {
          cin>>g[i][j];
          if(g[i][j]==0) g[i][j]=1e18;
          else if(g[i][j]==-1) g[i][j]=0;  
          st[i][j]=false;
        }        

        priority_queue<node>q;
        for(int j=2;j<=m;j++) if(g[1][j]!=1e18) q.push({1,j,g[1][j]}) ;
        for(int i=2;i<n;i++) if(g[i][m]!=1e18) q.push({i,m,g[i][m]}) ;

        ll res=1e18;
        while(q.size()){
            auto p=q.top();
            q.pop();
            int x=p.x,y=p.y;
            ll w=p.w;        
            if(y==1||x==n) {
                 res=min(res,w);  //弹出来的一定是最短的边 也即是最小花费的边
                 continue;   
             }

            if(st[x][y]) continue;

            st[x][y]=true;
            for(int i=0;i<4;i++){
                int xi=x+rou[i][0];
                int yi=y+rou[i][1];
                if(xi<1||xi>n||yi<1||yi>m||g[xi][yi]==1e18) continue;
                q.push({xi,yi,w+g[xi][yi]});
            }
        }

        if(res==1e18) puts("-1");
        else cout<<res<<endl;
    }

    return 0;
}