bfs
思路:三维标记状态 && 处理好 - | 和时刻的关系即可

 /*
bfs
思路:三维标记状态 && 处理好 - | 和时刻的关系即可
*/
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> PII;
#define MP(a,b) make_pair((a),(b))
const int inf = 0x3f3f3f3f;
const double pi=acos(-1.0);
const int dx[]={,-,,};
const int dy[]={,,,-};
const double eps = 1e-;
const int maxm = ;
const int maxn = ; struct Point {
int x,y,t;
};
Point s,e; bool vis[ maxn ][ maxn ][ ];
char mat[ maxn ][ maxn ];
queue<Point>q; int bfs( int n,int m ){
memset( vis,false,sizeof( vis ) );
while( !q.empty() )
q.pop();
Point cur = s;
vis[ s.x ][ s.y ][ s.t% ] = true;
q.push( cur );
while( !q.empty() ){
cur = q.front();
q.pop();
//printf("\ncur:[%d,%d] t = %d\n",cur.x,cur.y,cur.t);
if( cur.x==e.x && cur.y==e.y ){
e.t = min( e.t,cur.t );
}
if( cur.t>=e.t ) continue;
for( int i=;i<;i++ ){
Point nxt;
nxt.x = cur.x + dx[ i ];
nxt.y = cur.y + dy[ i ];
nxt.t = cur.t + ;
if( nxt.x<||nxt.x>=n||nxt.y<||nxt.y>=m ) continue;
if( mat[ nxt.x ][ nxt.y ]=='*' ) continue;
if( mat[ nxt.x ][ nxt.y ]=='.' ){
if( vis[ nxt.x ][ nxt.y ][ nxt.t% ]==true ) continue;
vis[ nxt.x ][ nxt.y ][ nxt.t% ] = true;
q.push( nxt );
//printf("0 nxt:[%d,%d] t = %d\n",nxt.x,nxt.y,nxt.t);
continue;
}//
nxt.x = cur.x + dx[ i ];
nxt.y = cur.y + dy[ i ];
nxt.t = cur.t + ;
if(( mat[ nxt.x ][ nxt.y ]=='-'&&cur.t%== )||( mat[ nxt.x ][ nxt.y ]=='|'&&cur.t%== )){
if( cur.x==nxt.x&&nxt.y>cur.y ) nxt.y = cur.y + ;
if( cur.x==nxt.x&&nxt.y<cur.y ) nxt.y = cur.y - ;
if( nxt.x>=&&nxt.x<n&&nxt.y>=&&nxt.y<m&&mat[ nxt.x ][ nxt.y ]=='.' ){
if( vis[ nxt.x ][ nxt.y ][ nxt.t% ]==false ){
vis[ nxt.x ][ nxt.y ][ nxt.t% ] = true;
q.push( nxt );
//printf("1 nxt:[%d,%d] t = %d\n",nxt.x,nxt.y,nxt.t);
continue;
}
}
}//1 ‘-’ 上下无需等待时间
nxt.x = cur.x + dx[ i ];
nxt.y = cur.y + dy[ i ];
nxt.t = cur.t + ;
/*恢复nxt很重要*/
if(( mat[ nxt.x ][ nxt.y ]=='-'&&cur.t%== )||( mat[ nxt.x ][ nxt.y ]=='|'&&cur.t%== )){
nxt.t = cur.t + ;
if( cur.x==nxt.x&&nxt.y>cur.y ) nxt.y = cur.y + ;
if( cur.x==nxt.x&&nxt.y<cur.y ) nxt.y = cur.y - ;
if( nxt.x>=&&nxt.x<n&&nxt.y>=&&nxt.y<m&&mat[ nxt.x ][ nxt.y ]=='.' ){
if( vis[ nxt.x ][ nxt.y ][ nxt.t% ]==false ){
vis[ nxt.x ][ nxt.y ][ nxt.t% ] = true;
q.push( nxt );
//printf("2 nxt:[%d,%d] t = %d\n",nxt.x,nxt.y,nxt.t);
continue;
}
}
}//2 ‘-’ 上下需要等待时间
nxt.x = cur.x + dx[ i ];
nxt.y = cur.y + dy[ i ];
nxt.t = cur.t + ;
/*恢复nxt很重要*/
if(( mat[ nxt.x ][ nxt.y ]=='|'&&cur.t%== )||( mat[ nxt.x ][ nxt.y ]=='-'&&cur.t%== )){
if( cur.y==nxt.y&&nxt.x>cur.x ) nxt.x = cur.x + ;
if( cur.y==nxt.y&&nxt.x<cur.x ) nxt.x = cur.x - ;
if( nxt.x>=&&nxt.x<n&&nxt.y>=&&nxt.y<m&&mat[ nxt.x ][ nxt.y ]=='.' ){
if( vis[ nxt.x ][ nxt.y ][ nxt.t% ]==false ){
vis[ nxt.x ][ nxt.y ][ nxt.t% ] = true;
q.push( nxt );
//printf("3 nxt:[%d,%d] t = %d\n",nxt.x,nxt.y,nxt.t);
continue;
}
}
}//3 ‘|’ 左右无需等待时间
nxt.x = cur.x + dx[ i ];
nxt.y = cur.y + dy[ i ];
nxt.t = cur.t + ;
/*恢复nxt很重要*/
if(( mat[ nxt.x ][ nxt.y ]=='|'&&cur.t%== )||( mat[ nxt.x ][ nxt.y ]=='-'&&cur.t%== )){
nxt.t = cur.t + ;
if( cur.y==nxt.y&&nxt.x>cur.x ) nxt.x = cur.x + ;
if( cur.y==nxt.y&&nxt.x<cur.x ) nxt.x = cur.x - ;
if( nxt.x>=&&nxt.x<n&&nxt.y>=&&nxt.y<m&&mat[ nxt.x ][ nxt.y ]=='.' ){
if( vis[ nxt.x ][ nxt.y ][ nxt.t% ]==false ){
vis[ nxt.x ][ nxt.y ][ nxt.t% ] = true;
q.push( nxt );
//printf("4 nxt:[%d,%d] t = %d\n",nxt.x,nxt.y,nxt.t);
continue;
}
}
}//4 ‘|’ 左右需要等待时间
}
}
return e.t;
} int main(){
int n,m;
//freopen( "in.txt","r",stdin );
while( scanf("%d%d",&n,&m)== ){
for( int i=;i<n;i++ ){
scanf("%s",mat[ i ]);
for( int j=;j<m;j++ ){
if( mat[ i ][ j ]=='S' ){
s.x = i;
s.y = j;
s.t = ;
mat[ i ][ j ] = '.';
}
else if( mat[ i ][ j ]=='T' ){
e.x = i;
e.y = j;
e.t = inf;
mat[ i ][ j ] = '.';
}
}
}
printf("%d\n",bfs( n,m ));
}
return ;
}

最新文章

  1. windows 安装mysql 步骤
  2. javascript:算法之斐波那契数列
  3. 调试技巧--Windows端口号是否被占用
  4. Java基础之一组有用的类——Observable和Observer对象(Horrific)
  5. iOS 引导页组件 HcdGuideView
  6. Windows Server2008+IIS7部署网站的日期格式问题
  7. 帝国cms内容页模版
  8. chrome浏览器和其它浏览器对scrollTop、scrollLeft的获取方法
  9. Mybatis3.2不支持Ant通配符TypeAliasesPackage扫描的解决方案
  10. DELPHI中MDI子窗口的关闭和打开
  11. SpringBoot整合redis哨兵主从服务
  12. C++解析四-友员函数、内联函数、静态成员
  13. VB.NET工作记录
  14. Win10 专业版激活!
  15. UVa 1658 海军上将(最小费用最大流)
  16. docker sshd image problem, session required pam_loginuid.so, cann&#39;t login
  17. STM32(11)——DMA
  18. ACM学习历程—HDU5701 中位数计数(中位数 &amp;&amp; 计数排序)
  19. modal html
  20. 跟阿根一起学Java Web开发一:开发环境搭建及JSPGen基础配置

热门文章

  1. 在win7下配置java编译环境变量
  2. sqlserver 大文件脚本执行
  3. c# Aes加解密和对象序列化
  4. SystemFile
  5. [Linux]学习笔记(1)
  6. OSI与TCP/IP模型之比较
  7. Android SDK离线安装方法详解(加速安装) 转
  8. 《WPF程序设计指南》读书笔记——第8章 依赖属性
  9. 约束的DEFERRABLE, NOT DEFERRABLE, INITIALLY IMMEDIATE 和 INITIALLY DEFERRED
  10. 编译升级php