首页 > 代码库 > hdu--1728--special bfs
hdu--1728--special bfs
发现 很多 bfs很有意思啊 做完刚那题后 随机切的这题
这边 我们要求出 到达坐标<x,y>的转弯次数 并且要不断地更新取最小值 直到在符合条件的转弯次数下 找到了出口
所以 这里对于 <x,y>的初始化很重要 就是将它初始化为Inf 尽量大点就是了
然后在bfs中 对于同方向走路的点和从起点开始i走 是不需要增加转弯次数的 另外 就是要增加一次转弯次数了
蛮有意思的 =_=
1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5 6 int n , m , k; 7 const int inf = 0x3f3f3f3f; 8 const int size = 110; 9 char mp[size][size];10 int cnt[size][size];11 int dir[4][2] = {-1,0,1,0,0,-1,0,1};12 struct node13 {14 int x , y , pos , T;15 node( ){};16 node( int u , int v , int w , int z ):x(u),y(v),pos(w),T(z){};17 };18 queue<node>q;19 20 void init()21 {22 memset( cnt , inf , sizeof(cnt) );23 while( !q.empty() )24 {25 q.pop();26 }27 }28 29 bool bfs( int x1 , int y1 , int x2 , int y2 )30 {31 node now;32 q.push( node(x1,y1,-1,0) );33 while( !q.empty() )34 {35 now = q.front();36 q.pop();37 if( now.x==x2 && now.y==y2 && now.T<=k )38 {39 return true;40 }41 for( int i = 0 ; i<4 ; i++ )42 {43 int x = now.x + dir[i][0];44 int y = now.y + dir[i][1];45 if( x>=1 && x<=n && y>=1 && y<=m && mp[x][y]!=‘*‘ )46 {47 if( now.pos==i || now.pos==-1 )48 {49 if( now.T <= cnt[x][y] )50 {51 cnt[x][y] = now.T;52 q.push( node( x , y , i , now.T ) );53 }54 }55 else 56 {57 if( now.T+1 <= cnt[x][y])58 {59 cnt[x][y] = now.T+1; 60 q.push( node( x , y , i , now.T+1 ) );61 }62 }63 }64 }65 }66 return false;67 }68 69 int main()70 {71 cin.sync_with_stdio(false);72 int t , x1 , y1 , x2 , y2;73 bool ans;74 cin >> t;75 while( t-- )76 {77 init();78 cin >> n >> m;79 for( int i = 1 ; i<=n ; i++ )80 {81 for( int j = 1 ; j<=m ; j++ )82 {83 cin >> mp[i][j];84 }85 }86 cin >> k >> y1 >> x1 >> y2 >> x2;87 ans = bfs( x1 , y1 , x2 , y2 );88 if( ans )89 cout << "yes" << endl;90 else91 cout << "no" << endl;92 }93 return 0;94 }
hdu--1728--special bfs
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。