发现 很多 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 node 13 { 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 else 91 cout << "no" << endl; 92 } 93 return 0; 94 }