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