[dijkstra堆優化+bfs] 迷宮2

​

題目描述

這是一個關于二維格子狀迷宮的題目。迷宮的大小為N*M，左上角格子座标為(1,1)、右上角格子座标為(1,M)、左下角格子座标為(N,1)、右下角格子座标為(N,M)。每一格都用-1到10^9之間的整數表示，意義分别為：-1為牆壁，0為走道，而1到10^9之間的正整數代表特殊的走道。

蜥蜴最初位于迷宮的座标(1,1)的格子，每一步蜥蜴隻能往上、下、左、右、左上、右上、左下、右下八個方向之一前進一格，并且，他也不能走出迷宮邊界。蜥蜴的目的地是走到迷宮的右下角格子，也就是座标位置(N,M)。我們想要動一些手腳，使得蜥蜴沒有辦法從(1,1)出發并抵達(N,M)。我們學會了一個邪惡的法術，這個法術可以把特殊的走道變成牆壁，施法一次的代價為表示該特殊走道的正整數。

假設，我們可以在蜥蜴出發之前不限次數的使用這個邪惡的法術，所花的總代價即為每次施法代價的總和，蜥蜴出發之後就不能再使用這個法術了，請問讓蜥蜴沒辦法達到終點所必須花費的最小總代價是多少呢？

注意，0所代表的走道是無法變為牆壁的。

輸入描述:

輸入的第一行有三個正整數Q,N,M。

代表接下來有Q組資料，這Q組資料都是N*M的迷宮。

接下來每組資料各N行，代表一個迷宮，每行各M個整數，第i行中的第j個整數代表迷宮座标(i,j)的格子。

輸出描述:

每一組資料輸出一行，如果無論如何蜥蜴都能到達終點，請在這一行中輸出-1，否則請在這一行中輸出一個代表答案的整數。

示例1

輸入

3 3 3

0 2 2

3 2 3

2 2 0

0 1 2

-1 1 -1

2 1 0

0 1 2

0 0 0

2 1 0

輸出

6

1

-1

備注:

1<=Q<=5*103

1<=Q*N*M<=2.5*105

1<=N,M<=500

代表迷宮格子的數字為介于-1和109間的整數(包含-1和109)

每個迷宮中，代表座标(1,1)和(N,M)的格子的數字一定是0

通過對題意的分析, 

若數字為零,無法改成障礙物,可以看做代價無限大; 若數字為-1,即已經是障礙,可以看做無需修改成本

怎麼才算是将起始點隔絕開呢?

通過遐想, 當障礙的一段位于上or右,另一端位于下or左時, 無疑是成功的分割方法

見下圖

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

typedef long long LL;
const int N = 510;
LL g[N][N];
int st[N][N];
int t, n, m;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1, 0};
struct point{
    int x, y;
    LL w;
    bool operator < (const point& b)const{
        return w > b.w;
    }
};

LL dij()
{
    LL res = 1e18;
    
    priority_queue<point> q;
    for(int i = 2; i <= m; i ++)
        if(g[1][i] != 1e18) q.push({1, i, g[1][i]});
    for(int i = 2; i < n; i ++)
        if(g[i][m] != 1e18) q.push({i, m, g[i][m]});
    
    while(q.size())
    {
        point t = q.top();
        q.pop();
        
        if(t.x==n || t.y==1){
            res = min(res, t.w);
            continue;
        }
        
        if(st[t.x][t.y]) continue;//不再重複處理
        st[t.x][t.y] = 1;
        
        for(int i = 0; i < 4; i ++)
        {
            int nx = t.x+dx[i], ny = t.y+dy[i];
            if(nx && ny && nx<=n && ny<= m && g[nx][ny]!=1e18)
            {
                q.push({nx, ny, t.w+g[nx][ny]});
            }
        }
    }
    return res;
}
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];
                //scanf("%ld", &g[i][j]);
                st[i][j] = 0;
                if(!g[i][j]) g[i][j] = 1e18;
                else if(!(g[i][j]+1)) g[i][j] = 0;
            }
        
        st[1][1] = st[n][m] = 1;
        LL res = dij();
        if(res == 1e18) printf("-1\n");
        else printf("%lld\n", res);
    }
    return 0;
}