http://acm.hdu.edu.cn/showproblem.php?pid=1728
題意:給出一張圖,轉彎數k,起點(x1,y1),(x2,y2)判斷能不能最多只轉k個彎時從起點走到終點
輸入時注意起點與終點是先y后x的
思路:用point[4][2]表示方向向量,每次遍歷遍歷一行或者一列,遍歷時要注意遇到遍歷過的點要跳過去,繼續遍歷他后面的點而不是直接結束.
? 由于每次遍歷一行所以并不需要記錄初始方向.
記錄轉彎次數則在每一取隊頭時,把轉彎數+1.
還是不懂得化去看看KIDx大牛的http://972169909-qq-com.iteye.com/blog/1244218
View Code 1 #include<iostream> 2 #include <queue> 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 <Node> 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"<<endl; 95 } 96 else 97 { 98 cout<<"no"<<endl; 99 } 100 } 101 return 0; 102 }
?
?
?
