input:maze.in output:maze.out

时间限制: 1000 ms 空间限制: 524288 KB

题目描述

输入

输出

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
3
2 2
S#
#T
2 5
SB###
##P#T
4 7
SP.....
P#.....
......#
B...##T

样例输出

1
2
3
-1
8
11

数据范围限制

提示

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
#define rr register
using namespace std;
int n,m,sx,sy,ex,ey,ans=(1<<30);
int mx[4]={1,0,0,-1};
int my[4]={0,1,-1,0};
char a[105][105];
bool f[105][105][6];
namespace dalao{
    int min(int a,int b)
    {
        if(a>b)
            return b;
        return a;
    }
}
struct state{
    int x,y,t,O2;
    bool operator < (const state &tmp) const{
        return t>tmp.t;
    }
}st;
priority_queue <state> heap;
inline void bfs()
{
    while(!heap.empty())
    {
        state u=heap.top();
        heap.pop();
        for(rr int i=0;i<4;i++)
        {
            state v;
            v.x=u.x+mx[i];
            v.y=u.y+my[i];
            v.O2=u.O2;
            v.t=u.t+1;
            if(v.x<1 || v.y<1 || v.x>n || v.y>m)
                continue;
            if(a[v.x][v.y]=='#')
            {
                if(v.O2) {
                    v.O2--;v.t++;
                }
                else
                    continue;
            }
            if(a[v.x][v.y]=='B')
            {
                if(v.O2<5) v.O2++;
            }
            if(a[v.x][v.y]=='P')
                v.t--;
            if(f[v.x][v.y][v.O2])
                continue;
            f[v.x][v.y][v.O2]=true;
            if(a[v.x][v.y]=='T')
                ans=dalao::min(ans,v.t);
            heap.push(v);
        }
    }
}
int main()
{
    freopen("maze.in","r",stdin);
    freopen("maze.out","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(f,false,sizeof f);
        memset(a,'\0',sizeof a);
        ans=(1<<30);
        scanf("%d %d",&n,&m);
        for(rr int i=1;i<=n;i++)
            for(rr int j=1;j<=m;j++)
            {
                scanf(" %c",&a[i][j]);
                if(a[i][j]=='S')
                {
                    st.x=i;
                    st.y=j;
                    st.t=0;
                    st.O2=0;
                }
            }
        heap.push(st);
        bfs();
        if(ans==(1<<30))
        ans=-1;
        printf("%d\n",ans);
    }
}