诡异的楼梯

Time Limit: 1000ms

Memory Limit: 65536KB

This problem will be judged on

HDU. Original ID:

64-bit integer IO format: %I64d      Java class name: Main

 

Hogwarts正式开学以后,Harry发现在Hogwarts里,某些楼梯并不是静止不动的，相反,他们每隔一分钟就变动一次方向.

比如下 面的例子里,一开始楼梯在竖直方向,一分钟以后它移动到了水平方向,再过一分钟它又回到了竖直方向.Harry发现对他来说很难找到能使得他最快到达目的 地的路线,这时Ron(Harry最好的朋友)告诉Harry正好有一个魔法道具可以帮助他寻找这样的路线,而那个魔法道具上的咒语,正是由你纂写的.

Input

测试数据有多组，每组的表述如下：

第一行有两个数,M和N,接下来是一个M行N列的地图,'*'表示障碍物,'.'表示走廊,'|'或者'-'表 示一个楼梯,并且标明了它在一开始时所处的位置:'|'表示的楼梯在最开始是竖直方向,'-'表示的楼梯在一开始是水平方向.地图中还有一个'S'是起 点,'T'是目标,0<=M,N<=20,地图中不会出现两个相连的梯子.Harry每秒只能停留在'.'或'S'和'T'所标记的格子内.

Output

只有一行,包含一个数T,表示到达目标的最短时间.

注意:Harry只能每次走到相邻的格子而不能斜走,每移动一次恰好为一分钟,并且Harry登上楼梯并经过楼梯到达对面的整个过程只需要一分钟,Harry从来不在楼梯上停留.并且每次楼梯都恰好在Harry移动完毕以后才改变方向.

Sample Input

5 5**..T**.*...|...*.*.S....

Sample Output

7

Hint

Hint

地图如下：

Source

 

解题：搜索呗..

 

1 #include 
        
           2 #include 
         
            3 #include 
          
             4 #include 
           
              5 #define pii pair
            
               6 #define mkp make_pair  7 using namespace std;  8 const int maxn = 110;  9 char mp[maxn][maxn]; 10 int n,m,sx,sy,tx,ty,d[maxn][maxn]; 11 const int dir[4][2] = {-1,0,0,-1,1,0,0,1}; 12 bool vis[maxn][maxn]; 13 bool isIn(int x,int y) { 14     return x >= 0 && x < n && y >= 0 && y < m; 15 } 16 int bfs() { 17     queue< pii >q; 18     memset(d,127,sizeof(d)); 19     memset(vis,false,sizeof(vis)); 20     vis[sx][sy] = true; 21     d[sx][sy] = 0; 22     q.push(mkp(sx,sy)); 23     while(!q.empty()) { 24         pii p = q.front(); 25         q.pop(); 26         for(int i = 0; i < 4; ++i) { 27             int ox = p.first + dir[i][0]; 28             int oy = p.second + dir[i][1]; 29             int nx = ox,ny = oy; 30             vis[p.first][p.second] = false; 31             if(isIn(ox,oy)) { 32                 if(mp[ox][oy] == '.') { 33                     if(d[p.first][p.second] + 1 < d[ox][oy]) { 34                         d[ox][oy] = d[p.first][p.second] + 1; 35                         if(!vis[ox][oy]) { 36                             q.push(mkp(ox,oy)); 37                             vis[ox][oy] = true; 38                         } 39                     } 40                 }else{ 41                     while(isIn(ox,oy)&&mp[ox][oy] == mp[nx][ny]) { 42                         ox += dir[i][0]; 43                         oy += dir[i][1]; 44                     } 45                     if(!isIn(ox,oy)||mp[ox][oy] == '#') continue; 46                     bool flag = false; 47                     if((i&1)&&(d[p.first][p.second]&1)&&mp[nx][ny] == '|'){ 48                         if(d[ox][oy] > d[p.first][p.second] + 1){ 49                             d[ox][oy] = d[p.first][p.second] + 1; 50                             flag = true; 51                         } 52                     } 53                     if(!(i&1) && (d[p.first][p.second]&1)&&mp[nx][ny] == '-'){ 54                         if(d[ox][oy] > d[p.first][p.second] + 1){ 55                             d[ox][oy] = d[p.first][p.second] + 1; 56                             flag = true; 57                         } 58                     } 59                     if((i&1)&&!(d[p.first][p.second]&1)&&mp[nx][ny] == '-'){ 60                         if(d[ox][oy] > d[p.first][p.second] + 1){ 61                             d[ox][oy] = d[p.first][p.second] + 1; 62                             flag = true; 63                         } 64                     } 65                     if(!(i&1)&&!(d[p.first][p.second]&1)&&mp[nx][ny] == '|'){ 66                         if(d[ox][oy] > d[p.first][p.second] + 1){ 67                             d[ox][oy] = d[p.first][p.second] + 1; 68                             flag = true; 69                         } 70                     } 71                     if((i&1)&&(d[p.first][p.second]&1)&&mp[nx][ny] == '-'){ 72                         if(d[ox][oy] > d[p.first][p.second] + 2){ 73                             d[ox][oy] = d[p.first][p.second] + 2; 74                             flag = true; 75                         } 76                     } 77                     if((i&1)&&!(d[p.first][p.second]&1)&&mp[nx][ny] == '|'){ 78                         if(d[ox][oy] > d[p.first][p.second] + 2){ 79                             d[ox][oy] = d[p.first][p.second] + 2; 80                             flag = true; 81                         } 82                     } 83                     if(!(i&1)&&!(d[p.first][p.second]&1)&&mp[nx][ny] == '-'){ 84                         if(d[ox][oy] > d[p.first][p.second] + 2){ 85                             d[ox][oy] = d[p.first][p.second] + 2; 86                             flag = true; 87                         } 88                     } 89                     if(!(i&1)&&(d[p.first][p.second]&1)&&mp[nx][ny] == '|'){ 90                         if(d[ox][oy] > d[p.first][p.second] + 2){ 91                             d[ox][oy] = d[p.first][p.second] + 2; 92                             flag = true; 93                         } 94                     } 95                     if(flag && !vis[ox][oy]){ 96                         vis[ox][oy] = true; 97                         q.push(mkp(ox,oy)); 98                     } 99                 }100             }101         }102     }103     return d[tx][ty];104 }105 int main() {106     while(~scanf("%d %d",&n,&m)){107         for(int i = 0; i < n; ++i){108             scanf("%s",mp[i]);109             for(int j = 0; j < m; ++j)110             if(mp[i][j] == 'S') mp[sx = i][sy = j] = '.';111             else if(mp[i][j] == 'T') mp[tx = i][ty = j] = '.';112         }113         printf("%d\n",bfs());114     }115     return 0;116 }