2019 校内赛 RPG的地牢猎手(bfs+优先队列)

Problem Description

Luke最近沉迷一款RPG游戏，游戏中角色可以进入地牢关卡，只要顺利走出地牢就可以获得奖励。
地牢表示为n行m列的块矩阵，其中每个块只可以是障碍块、入口、出口或数字块，角色不能通过障碍块，其余块均可任意通行，角色经过数字块时疲劳度会增加相应的数字（经过出入口不产生疲劳）。
地牢有若干入口和1个出口，角色可以任意选择入口。
抵达出口时的疲劳值越少，地牢提供的奖励越多，为了尽可能获得更多的奖励，问从进入地牢到离开地牢所产生的疲劳值最少是多少，如果无法抵达出口，输出-1。
图示：障碍块 ’X’，数字块 ’0’~’9’，入口 ‘S’，出口 ‘E’。

Input

第一行为正整数t表示测试组数。
随后为t组输入，每组测试中，第一行为矩阵行列数n m，随后n行长度为m的字符串表示地牢。
t<=100
1<=n,m<=100

Output

每组测试输出一行表示最小的疲劳度，如果无法抵达出口则输出-1。

Sample Input

3 3

SXS

123

XEX

Sample Output

思路:因为只有一个终点所以从终点开始搜索每次用优先队列弹出最优点的情况

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<string>

#include<vector>

#include<stack>

#include<bitset>

#include<cstdlib>

#include<cmath>

#include<set>

#include<list>

#include<deque>

#include<map>

#include<queue>

#define ll long long int

using namespace std;

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int moth[]={,,,,,,,,,,,,};

int dir[][]={, ,, ,-, ,,-};

int dirs[][]={, ,, ,-, ,,-, -,- ,-, ,,- ,,};

const int inf=0x3f3f3f3f;

const ll mod=1e9+;

int n,m;

char G[][];

bool vis[][];

int ans;

struct node{

    int x,y,v;

    friend operator < (node a,node b){

        return a.v>b.v;

    }

};

void bfs(int ex,int ey){

    priority_queue<node> q;

    node t; t.x=ex; t.y=ey; t.v=;

    q.push(t);

    while(!q.empty()){

        node temp=q.top();

        q.pop();

        if(G[temp.x][temp.y]=='S'){

            ans=temp.v;

            return ;

        }

        for(int i=;i<;i++){

            int xx=temp.x+dir[i][];

            int yy=temp.y+dir[i][];

            if(xx>=&&xx<=n&&yy>=&&yy<=m&&!vis[xx][yy]&&G[xx][yy]!='X'){

                vis[xx][yy]=;

                node tt; tt.x=xx; tt.y=yy;

                if(G[xx][yy]>=''&&G[xx][yy]<='')

                tt.v=temp.v+G[xx][yy]-'';

                else tt.v=temp.v;

                q.push(tt);

            }

        }

    }

    ans=-;

}

int main(){

    ios::sync_with_stdio(false);

    //freopen("in.txt","r",stdin);

    int t;

    cin>>t;

    while(t--){

        memset(vis,,sizeof(vis));

        cin>>n>>m;

        int ex,ey;

        for(int i=;i<=n;i++)

            for(int j=;j<=m;j++){

                cin>>G[i][j];

                if(G[i][j]=='E')

                    ex=i,ey=j;

            }

        bfs(ex,ey);

        cout<<ans<<endl;

    }

    return ;

}