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);
}
}