题意:给一幅图,图中有 'S'  'T'  '|'  '-'  '*'  '.'  几种符号,

　　'*'表示墙　　'.'表示路　　'S' 表示 起点.    'T'表示 终点  '|'或者'-' 表示楼梯

　　楼梯每过一分钟就会改变一次方向(每走一格一分钟),不能停留在楼梯上且经过楼梯不需要时间.

　　求起点到终点最少需要多少时间.

输入:先输入x y 表示x行 y列

　　接下来是x行y列的图

输出:输出最少的时间

 

由于楼梯存在两种状态,所以不能直接使用普通的队列(好像是可以的),所以使用优先队列.

一开始的思路是遇到楼梯则判断楼梯状态,若能通过则直接过去,不能通过则再加一步(等待的时间)再过去.

但这样可能会出现下面的问题.

若右下在队头则会出现5步,5步不是最优解.

所以在遇到楼梯且不能通过时,应该原地等一步而不是直接跳过去.(即吧当前队头重新放入队列中.注意是队头而不是加了方向向量的位置.)

 

1 #include 
      
         2 #include 
       
          3 using namespace std;  4 const int MAX = 20 + 5;  5 char map[MAX][MAX];  6 int point[4][2] = {-1,0,0,-1,1,0,0,1};//上 左 下 右  7 struct Node  8 {  9     int x; 10     int y; 11     int step; 12     friend bool operator< (const Node &a,const Node &b) 13     { 14         return a.step > b.step; 15     } 16 }; 17 int judge(Node a_k,int i_k) 18 { 19     if(map[a_k.x][a_k.y] == '|') 20     { 21         if(i_k%2 == 0)//上下走 22         { 23             if(a_k.step % 2 == 0)//变 24             { 25                 return 0; 26             } 27             else//不变 28             { 29                 return 1; 30             } 31         } 32         else//左右走 33         { 34             if(a_k.step % 2 == 0)//变 35             { 36                 return 1; 37             } 38             else//不变 39             { 40                 return 0; 41             } 42         } 43     } 44     else 45     { 46         if(map[a_k.x][a_k.y] == '-') 47         { 48             if(i_k%2 == 0)//上下走 49             { 50                 if(a_k.step%2 == 0)//变 51                 { 52                     return 1; 53                 } 54                 else//不变 55                 { 56                     return 0; 57                 } 58             } 59             else//左右走 60             { 61                 if(a_k.step%2 == 0)//变 62                 { 63                     return 0; 64                 } 65                 else//不变 66                 { 67                     return 1; 68                 } 69             } 70         } 71     } 72 } 73 int x,y; 74 int BFS(Node a,Node b) 75 { 76     priority_queue 
        
          q; 77     a.step = 0; 78     q.push(a); 79     map[a.x][a.y] = '*'; 80     while(!q.empty()) 81     { 82         Node mid; 83         mid = q.top (); 84         if(mid.x== b.x && mid.y == b.y) 85         { 86             cout<
         
          <
          
           = 1 && a.y >= 1 && map[a.x][a.y] != '*') 98             { 99                 if(map[a.x][a.y] == '.' || map[a.x][a.y] == 'T')100                 {101                     map[a.x][a.y] = '*';102                     q.push(a);103                 }104                 else105                 {106                     if(map[a.x][a.y] == '|' || map[a.x][a.y] == '-')107                     {108                         if(judge(a,i))109                         {110                             a.x = a.x + point[i][0];111                             a.y = a.y + point[i][1];112                             if( map[a.x][a.y] != '*')113                             {114                                 if(map[a.x][a.y] == '.' || map[a.x][a.y] == 'T')115                                 {116                                     map[a.x][a.y] = '*';117                                     q.push (a);118                                 }119                             }120                         }121                         else122                         {123                             q.push (mid);//小心不要写成q.push(a)124                         }125                     }126                 }127             }128         }129     }130 }131 int main()132 {133     while(cin>>x>>y)134     {135         memset(map,0,sizeof(map));136         int i,j;137         Node s,e;138         for(i=1;i<=x;i++)139         {140             for(j=1;j<=y;j++)141             {142                 cin>>map[i][j];143                 if(map[i][j] == 'S')144                 {145                     s.x = i;146                     s.y = j;147                 }148                 if(map[i][j] == 'T')149                 {150                     e.x = i;151                     e.y = j;152                 }153             }154         }155         BFS(s,e);156     }157     return 0;158 }