走迷宫升级版——边的权值不同

单点时限: 2.0 sec
内存限制: 256 MB
一天，sunny 不小心进入了一个迷宫，不仅很难寻找出路，而且有的地方还有怪物，但是 sunny 有足够的能力杀死怪物，但是需要一定的时间，但是 sunny 想早一点走出迷宫，所以请你帮助他计算出最少的时间走出迷宫，输出这个最少时间。

我们规定每走一格需要时间单位 1, 杀死怪物也需要时间 1, 如果不能走到出口，则输出 impossible. 每次走只能是上下左右 4 个方向。

输入格式
每次首先 2 个数 n,m (0<n,m≤200)，代表迷宫的高和宽，然后 n 行，每行 m 个字符。

S 代码你现在所在的位置。
T 代表迷宫的出口。
‘#’ 代表墙，你是不能走的。
X 代表怪物。
. 代表路，可以走。
处理到文件结束。

输出格式
输出最少的时间走出迷宫。不能走出输出 impossible。

样例
输入样例：
4 4
S.X.
#…#
…#.
X…T
4 4
S.X.
#…#
…#.
X.#T
输出样例：
6
impossible

算法 (BFS + 优先队列) 题意：走迷宫，求最短路径，上下左右走一格花费1，走到有怪的格子花费2.

思路：将每一点的坐标和由起点到该点的距离存入结构体.
由起点开始，将该点存入优先队列，以到起点的距离dis为优先级，每次取出dis最小的，向外扩散。
相当于第一轮得出所有到起点距离为1的点，第二轮得出所有到起点距离为2的点。
注意：对普通的最短路问题，由于每个各自的花费相同，因此每次存入的点优先级都相同.
故不需要使用优先队列，但本题存在有无怪物的区别，每次存入的格子的优先级可能不同，故使用优先队列。

const int N = 15;
int n, m;
int sx, sy, ex, ey;
char g[N][N];

struct po
{
    int x, y, dis;
};

int dx[]{0, 1, 0, -1} ,dy[]{1, 0, -1, 0};

bool operator <(const po&a,const po&b){
    return a.dis > b.dis;
}

int bfs(){
    priority_queue<po> q;
    q.push({sx, sy, 0});
    g[sx][sy] = '#';
    while(!q.empty()){
        auto t = q.top();
        q.pop();
        int dis = t.dis;

        if(t.x==ex&&t.y==ey){
            return dis;
        }

        for (int i = 0; i < 4;i++){
            int x = t.x + dx[i], y = t.y+dy[i];
            if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]!='#' ){
                if(g[x][y]=='.'||g[x][y]=='T'){
                dis = t.dis + 1;
                }
                if(g[x][y]=='X'){
                dis = t.dis + 2;
                }
                g[x][y] = '#';
                q.push({x,y,dis});
            }
        }
    }
    return -1;
}

int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
    char c;
    cin >> c;
    if(c=='S'){
        sx = i, sy = j;}
        if(c=='T'){
            ex = i, ey = j;}
        g[i][j] = c;
    }
    int re = bfs();
    if(re==-1){
        cout << "impossible";
    }
    else{
        cout << re;
    }
    }
    
}