1 #include<iostream>    2 #include<cstdio>    3 #include<cstring>    4 #include<algorithm>    5 #include<queue>    6     7 using namespace std;    8     9 struct node   10 {   11     int x,y,t;   12     bool operator<(const node& a)const   13     {   14         return t>a.t;   15     }   16 };   17    18 int n,m;   19 char g[30][30];   20 bool vis[30][30];   21 int x1,y1,x2,y2;   22 int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};   23    24 bool jud(node k)   25 {   26     if(k.x<0||k.x>=n||k.y<0||k.y>=m)   27         return false;   28     if(g[k.x][k.y]==‘*‘)   29         return false;   30     if(vis[k.x][k.y])   31         return false;   32     return true;   33 }   34    35 int bfs()   36 {   37     node a,k;   38     priority_queue<node> q;   39     a.x=x1,a.y=y1,a.t=0;   40     q.push(a);   41     vis[x1][y1]=1;   42     while(!q.empty())   43     {   44         a=q.top();   45         q.pop();   46         for(int i=0;i<4;i++)   47         {   48             if(g[a.x][a.y]==‘-‘ && a.t%2==0 && (i==2||i==3)) continue; //从前面(后面)过不去 49             if(g[a.x][a.y]==‘-‘ && a.t%2==1 && (i==0||i==1)) continue;  //从前面(后面)过不去 50             if(g[a.x][a.y]==‘|‘ && a.t%2==0 && (i==0||i==1)) continue;  //从上面(下面)过不去 51             if(g[a.x][a.y]==‘|‘ && a.t%2==1 && (i==2||i==3)) continue;  //从上面(下面)过不去 52             k.x=a.x+dir[i][0];   53             k.y=a.y+dir[i][1];   54             k.t=a.t+1;   55             if(!jud(k)) continue;//该点不可通过或者出界   56             if(g[k.x][k.y]==‘-‘)   57             {   58                 if(a.t%2==0 && (i==3||i==2))  //不能过,等一秒; 59                 {   60                     q.push(k);   61                     continue;   62                 }   63                 else if(a.t%2==1 && (i==0||i==1))   64                 {   65                     q.push(k);   66                     continue;   67                 }   68                 else   69                 {   70                     k.t--;  //能过,这点不算时间;(计时从改楼梯开始); 71                     q.push(k);   72                     continue;   73                 }   74             }   75             if(g[k.x][k.y]==‘|‘)  //同‘-‘ 76             {   77                 if(a.t%2==0 && (i==0||i==1))   78                 {   79                     q.push(k);   80                     continue;   81                 }   82                 else if(a.t%2==1 && (i==2||i==3))   83                 {   84                     q.push(k);   85                     continue;   86                 }   87                 else   88                 {   89                     k.t--;   90                     q.push(k);   91                     continue;   92                 }   93             }   94             if(k.x==x2 && k.y==y2)   95                 return k.t;   96             vis[k.x][k.y]=1;  //‘.‘的点; 97             q.push(k);   98         }   99     }  100     return -1;  101 }  102   103 int main()  104 {  105     //freopen("1180.txt","r",stdin);106     while(~scanf("%d%d",&n,&m))  107     {  108         int i,j;109         gets(g[0]);  110         for( i=0;i<n;i++)  111             gets(g[i]);  112         for( i=0;i<n;i++)  113             for( j=0;j<m;j++)  114                 if(g[i][j]==‘S‘)  115                     x1=i,y1=j;  116                 else if(g[i][j]==‘T‘)  117                     x2=i,y2=j;  118         memset(vis,0,sizeof(vis));  119         int ans=bfs();  120         printf("%d\n",ans);  121   122   123     }  124     return 0;  125 }  

 1 #include<iostream> 2 #include<queue> 3 using namespace std; 4 #define maxn 21 5 char maze[maxn][maxn]; 6 int m,n,si,sj,ti,tj; 7 bool visited[maxn][maxn]; 8 int dir[][2] = {{0,-1},{1,0},{0,1},{-1,0}}; 9 struct node10 {11     int x,y,t;12 };13 bool ok(int i,int j)14 {15     if(i >= 1 && i <= m && j >= 1 && j <= n && maze[i][j] != ‘*‘ && !visited[i][j])16         return true;17     return false;    18 }19 bool canThrough(int i,int j,int dir,int step) //判断能否通过楼梯20 {21     int t;22     if(maze[i][j]==‘|‘)//若为‘|’，设t=123         t=1;24     else25         t=0;
26     if(step%2)//经过奇数秒后楼梯方向发生变化27         t++;28     if((t + dir)%2 == 0)//若楼梯的方向和寻找的方向相同29         return 1;30     return 0;31 }32 void BFS()33 {34     queue<node> Q;35     node p,q;36     p.x = si,p.y = sj,p.t = 0;37     Q.push(p);38     memset(visited,false,sizeof(visited));39     visited[p.x][p.y] = true;40     while(!Q.empty())41     {42         p = Q.front();43         Q.pop();44         if(p.x == ti && p.y == tj)45         {46             printf("%d\n",p.t);47             return;48         }49         for(int i = 0; i < 4; i++)50         {51             q.x = p.x+dir[i][0],q.y = p.y+dir[i][1],q.t = p.t+1;52             if(ok(q.x,q.y))         //若合法53             {54                 if(maze[q.x][q.y] == ‘.‘ || maze[q.x][q.y] == ‘T‘)55                     Q.push(q),visited[q.x][q.y] = true;56                 else57                 {58                     if(canThrough(q.x,q.y,i,p.t))  //如果能通过此楼梯，注意时间是p.t，因为q.t在之前以加159                     {60                         q.x += dir[i][0],q.y += dir[i][1];  //通过此楼梯的方向仍为i61                         if(ok(q.x,q.y))62                             Q.push(q),visited[q.x][q.y] = true;63                     }64                     else                            //通不过此楼梯，则再等一秒65                     { 66                         q.x += dir[i][0],q.y += dir[i][1];67                         if(ok(q.x,q.y))68                             p.t++,Q.push(p);69                     }70                 }71             }72         }73     }74 }75 int main()76 {77     //freopen("1001.txt","r",stdin);78     while(scanf("%d%d",&m,&n) != EOF)79     {80         int i,j;81         for(i = 1; i <= m; i++)82             for(j = 1; j <= n; j++)83             {84                 cin >> maze[i][j];85                 if(maze[i][j] == ‘S‘)86                     si = i, sj = j;87                 if(maze[i][j] == ‘T‘)88                     ti = i,tj = j;89             }90         BFS();91     }92     return 0;93 }