题意:给出一张图,转弯数k,起点(x1,y1),(x2,y2)判断能不能最多只转k个弯时从起点走到终点
输入时注意起点与终点是先y后x的
思路:用point[4][2]表示方向向量,每次遍历遍历一行或者一列,遍历时要注意遇到遍历过的点要跳过去,继续遍历他后面的点而不是直接结束.
由于每次遍历一行所以并不需要记录初始方向.
记录转弯次数则在每一取队头时,把转弯数+1.
还是不懂得化去看看KIDx大牛的
View Code 1 #include2 #include 3 using namespace std; 4 const int MAX = 100 + 10; 5 const int INF = 0x3fffffff; 6 char map[MAX][MAX]; 7 int used[MAX][MAX]; 8 int point[4][2]={ { 0,1},{ 1,0},{ 0,-1},{-1,0}};// 9 struct Node 10 { 11 int x; 12 int y; 13 int turn; 14 }; 15 int x,y; 16 int BFS(Node a,Node b) 17 { 18 memset(used,0,sizeof(used)); 19 queue q; 20 a.turn = -1; 21 q.push(a); 22 used[a.x][a.y] = 1; 23 while(!q.empty()) 24 { 25 Node mid; 26 mid = q.front(); 27 28 q.pop(); 29 if(mid.x == b.x && mid.y == b.y) 30 { 31 b.turn = mid.turn; 32 } 33 int i; 34 mid.turn++; 35 for(i=0;i<4;i++) 36 { 37 38 a.x = mid.x + point[i][0]; 39 a.y = mid.y + point[i][1]; 40 a.turn = mid.turn; 41 42 while(1) 43 { 44 if(map[a.x][a.y]!='*' && a.x>0 && a.y>0 && a.x<=x && a.y<=y) 45 { 46 if( used[a.x][a.y] == 1 ) 47 { 48 a.x = a.x + point[i][0]; 49 a.y = a.y + point[i][1]; 50 51 } 52 else 53 { 54 55 q.push(a); 56 used[a.x][a.y] = 1; 57 a.x = a.x + point[i][0]; 58 a.y = a.y + point[i][1]; 59 60 } 61 } 62 else 63 { 64 break; 65 } 66 } 67 } 68 } 69 return b.turn; 70 } 71 72 int main() 73 { 74 int T; 75 cin>>T; 76 while(T--) 77 { 78 memset(map,0,sizeof(map)); 79 cin>>x>>y; 80 int i,j; 81 for(i=1;i<=x;i++) 82 { 83 for(j=1;j<=y;j++) 84 { 85 cin>>map[i][j]; 86 } 87 } 88 int k; 89 Node a,b; 90 cin>>k>>a.y>>a.x>>b.y>>b.x; 91 b.turn = INF; 92 if( BFS(a,b) <= k) 93 { 94 cout<<"yes"<