1 #include<iostream>  2 #include<cstdio>  3 #include<cstdlib>  4 #include<cmath>  5 #include<cstring>  6 #include<queue>  7 using namespace std;  8 int m,n;  9 int xi,xj,yi,yj; 10 char map[25][25]; 11 int vis[25][25]; 12 int dir[4][2]={{0,1},{0,-1},{-1,0},{1,0}}; 13 struct ln{ 14     int x; 15     int y; 16     int step; 17 }abc,q; 18 int border(int x,int y) 19 { 20     if(x>=1&&x<=m && y>=1&&y<=n &&!vis[x][y] &&map[x][y]!=‘*‘) 21     return 1; 22     return 0; 23 } 24 int bfs() 25 { 26     memset(vis,0,sizeof(vis)); 27     int i; 28     queue<struct ln>p; 29     abc.x=xi; 30     abc.y=xj; 31     abc.step=0; 32     vis[abc.x][abc.y]=1; 33     p.push(abc); 34     while(p.empty()) 35     { 36         abc=p.front(); 37         p.pop(); 38         if(abc.x==yi && abc.y==yj) 39         { 40             return abc.step; 41         } 42         for(i=0;i<4;i++) 43         { 44             q.x=abc.x+dir[i][0]; 45             q.y=abc.y+dir[i][1]; 46             if(border(q.x,q.y)) 47             { 48                 if(map[q.x][q.y]==‘.‘||map[q.x][q.y]==‘T‘) 49                 { 50                     q.step=abc.step+1; 51                     vis[q.x][q.y]=1; 52                     p.push(q); 53                 } 54                 else if(map[q.x][q.y]==‘|‘) 55                 { 56                     if((abc.step+1)%2==0) 57                     { 58                         if(i==0||i==1) 59                         { 60                             q.step=abc.step; 61                             vis[q.x][q.y]=1; 62                             p.push(q); 63                         } 64                     } 65                     else 66                     { 67                         if(i==2||i==3) 68                         { 69                             q.step=abc.step; 70                             vis[q.x][q.y]=1; 71                             p.push(q); 72                         } 73                     } 74                 } 75                 else if(map[q.x][q.y]==‘-‘) 76                 { 77                     if((abc.step+1)%2==0) 78                     { 79                         if(i==2||i==3) 80                         { 81                             q.step=abc.step; 82                             vis[q.x][q.y]=1; 83                             p.push(q); 84                         } 85                     } 86                     else 87                     { 88                         if(i==0||i==1) 89                         { 90                             q.step=abc.step; 91                             vis[q.x][q.y]=1; 92                             p.push(q); 93                         } 94                     } 95                 } 96             } 97             //判断完一个方向 98         } 99         //走完100     }101     return 0;102 }103 104 int main()105 {106     while(~scanf("%d%d",&m,&n))107     {108         int i,j;109         for(i=1;i<=m;i++)110         {111             getchar();112             for(j=1;j<=n;j++)113             {114                 scanf("%c",&map[i][j]);115                 if(map[i][j]==‘S‘)116                 {117                     xi=i;118                     xj=j;119                 }120                 if(map[i][j]==‘T‘)121                 {122                     yi=i;123                     yj=j;124                 }125             }126         }127         int flag=0;128         flag=bfs();129         printf("%d\n",flag);130     }131     return 0;132 }