UESTC OJ 149 解救小Q - dblank

UESTC OJ 149 解救小Q

解救小Q
Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
Submit Status
小Q被邪恶的大魔王困在了迷宫里,love8909决定去解救她。 迷宫里面有一些陷阱,一旦走到陷阱里,就会被困身亡:(,迷宫 里还有一些古老的传送阵,一旦走到传送阵上,会强制被传送到 传送阵的另一头。

现在请你帮助love8909算一算,他至少需要走多少步才能解 救到小Q?
Input
第一行为一个整数TT,表示测试数据组数。

每组测试数据第一行为两个整数NN,MM,(1≤N,M≤501≤N,M≤50)表示 迷宫的长和宽。

接下来有NN行,每行MM个字符,是迷宫的具体描述。

.表示安全的位置

表示陷阱,

Q表示小Q的位置
L表示love8909所在位置,
数据保证love8909只有一个,数据也保证小Q只有一个。

小写字母a-z表示分别表示不同的传送阵,数据保证传送阵 两两配对。
Output
每组数据输出一行,解救小Q所需的最少步数,如果无论如何都 无法救小Q,输出-1。
Sample input and output
Sample Input
Sample Output
2

5 5
....L
.###.
b#b#a

.

...Qa

5 5
....L
.###.
.#.#.

.

...Q.
3
-1

思路:直接优先队列bfs,注意传送门可能因为方向原因到达多次

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e3 + 10, Mod = 100000007;
typedef long long ll;
int run[][2] = {1,0,0,1,0,-1,-1,0}, visN;
char sN;
map<pair<int, int>, pair<int, int> > mp;
int ss[30], n, m, fx, fy;
struct node
{
    int x, y, t;
    node() {}
    bool operator < (const node & P)const
    {
        return t > P.t;
    }
    node(int _x, int _y, int _t)
    {
        x = _x;
        y = _y;
        t = _t;
    }
};
vector<node>v[30];
int yes(int x, int y)
{
    if(x>=1&&x<=n && y>=1 && y<=m && !visx && sx!='#')
        return 1;
    return 0;
}
int bfs()
{
    priority_queue<node> q;
    node in, out;
    in.x = fx, in.y = fy, in.t = 0;
    q.push(in);
    visfx = 1;
    while(!q.empty())
    {
        in = q.top();
        q.pop();
        if(sin.x == 'L')
            return in.t;
        for(int i  = 0; i<4; i++)
        {
            out.x = in.x + runi;
            out.y = in.y + runi;
            if(yes(out.x, out.y))
            {
                if(sout.x >= 'a' && sout.x<='z')
                {
                    int x = out.x , y = out.y;
                    out.x = mp[make_pair(x, y)].first;
                    out.y = mp[make_pair(x, y)].second;
                    out.t = in.t + 1;
                    q.push(out);
                }
                else
                {
                    out.t = in.t + 1;
                    visout.x = 1;
                    q.push(out);
                }
            }
        }
    }
    return -1;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        memset(vis, 0, sizeof(vis));
        memset(ss, 0, sizeof(ss));
        scanf("%d%d", &n, &m);
        for(int  i = 0; i<30; i++)
            v[i].clear();
        for(int i = 1; i<=n; i++)
            for(int j = 1; j<=m; j++)
            {
                scanf(" %c", &si);
                if(si == 'Q')
                    fx = i, fy = j;
                if(si>='a' && si <= 'z')
                {
                    int sb = si - 'a';
                    v[sb].push_back(node(i, j, 0));
                }
            }
        for(int i = 0; i<26; i++)
        {
            if(v[i].size())
            {
                for(int j = 0; j<2; j++)
                {
                    mpmake_pair(v[i.x, vi.y)] = make_pair(vi.x, vi.y);
                }
            }
        }
        printf("%dn",bfs());
    }
    return 0;
}

 

相关文章

已有 6 条评论
  1. Personal Loans

    loans instant approval loans for good credit loans instant approval online loans bad credit instant approval

    Personal Loans 回复
  2. Instant Online Loans

    payday loans in ohio installment loans no credit installment loan bad credit installment loans

    Instant Online Loans 回复
  3. Online Payday Loan

    cashnowoffer tracking online registration loans instant approval guaranteed bad credit loans payday loans no credit check

    Online Payday Loan 回复
  4. Best Payday Loan

    personal loans loans personal personal loans personal loans for poor credit

    Best Payday Loan 回复
  5. Guesthaume

    guest test post
    bbcode
    html
    http://temresults2018.com/ simple

    Guesthaume 回复
  6. Online Loan

    easy money payday loans cash loans get cash now payday loans albuquerque

    Online Loan 回复
发表新评论