在线冲值

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<vector>
 8 using namespace std;
 9 struct node
10 {
11     int x,y,step;
12     friend bool operator <(node s1,node s2)
13     {
14         return s1.step>s2.step;
15     }
16 };
17 char a[305][305];
18 int bx,by,n,m,visited[305][305],b[4][2]={0,-1,0,1,-1,0,1,0};
19 int ans=1000000;
20 priority_queue<node>Q;
21 void BFS(int x,int y)
22 {
23     node q;
24    // q={x,y,0};
25     q.x=x;
26     q.y=y;
27     q.step=0;
28     Q.push(q);
29     while(!Q.empty())
30     {
31         node e=Q.top();
32         for(int i=0;i<4;i++)
33         {
34             node w;
35             w.x=e.x+b[i][0];
36             w.y=e.y+b[i][1];
37             if(w.x>=0&&w.x<m&&w.y>=0&&w.y<n&&a[w.y][w.x]!=‘R‘&&a[w.y][w.x]!=‘S‘&&!visited[w.y][w.x])
38             {
39                 visited[w.y][w.x]=1;
40                 if(a[w.y][w.x]==‘B‘)
41                 {
42                     w.step=e.step+2;
43                     Q.push(w);
44                 }
45                 else
46                 {
47                     w.step=e.step+1;
48                     Q.push(w);
49                 }
50                 if(a[w.y][w.x]==‘T‘)
51                 {
52                     ans=w.step;
53                     break;
54                 }
55             }
56             if(ans!=1000000)
57                 break;
58         }
59         Q.pop();
60     }
61     while(!Q.empty())
62         Q.pop();
63 }
64 int main()
65 {
66     while(scanf("%d%d",&n,&m),(n||m))
67     {
68         memset(a,‘\0‘,sizeof(a));
69         memset(visited,0,sizeof(visited));
70         for(int i=0;i<n;i++)
71             for(int j=0;j<m;j++)
72         {
73             scanf(" %c",&a[i][j]);
74             if(a[i][j]==‘Y‘)
75             {
76                 bx=j;
77                 by=i;
78             }
79         }
80         ans=1000000;
81         visited[by][bx]=1;
82         BFS(bx,by);
83         if(ans==1000000)
84             printf("-1\n");
85         else
86             printf("%d\n",ans);
87     }
88 }