首页 > 代码库 > PAT Mooc datastructure 6-1
PAT Mooc datastructure 6-1
Saving James Bond - Hard Version
This time let us consider the situation in the movie "Live and Let Die" in which James Bond, the world‘s most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape -- he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head... Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot).
Assume that the lake is a 100 by 100 square one. Assume that the center of the lake is at (0,0) and the northeast corner at (50,50). The central island is a disk centered at (0,0) with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him a shortest path to reach one of the banks. The length of a path is the number of jumps that James has to make.
Input Specification:
Each input file contains one test case. Each case starts with a line containing two positive integers N (<=100), the number of crocodiles, and D, the maximum distance that James could jump. Then N lines follow, each containing the (x, y) location of a crocodile. Note that no two crocodiles are staying at the same position.
Output Specification:
For each test case, if James can escape, output in one line the minimum number of jumps he must make. Then starting from the next line, output the position (x, y) of each crocodile on the path, each pair in one line, from the island to the bank. If it is impossible for James to escape that way, simply give him 0 as the number of jumps. If there are many shortest paths, just output the one with the minimum first jump, which is guaranteed to be unique.
Sample Input 1:
17 1510 -2110 21-40 1030 -5020 4035 100 -10-25 2240 -40-30 30-10 220 1125 2125 1010 1010 35-30 10
Sample Output 1:
40 1110 2110 35
1.题目分析
这个题目就是典型的最短路径问题~
使用BFS对图进行层级遍历，只要在任一层发现可以跳出的话，那么就逆序打印出来全体路径。
至于这个层次的问题，其实很好实现，因为在BFS入队的过程中，是将一个节点的链接节点依此入队。在入队的时候，只要将此节点的步点数加1写入下一层中即可完成层数的累积。
同时，为了完成最后的打印工作，需要使用一个数组，完成类似于链表的工作。每次压入新的节点时，就要将新节点对应的父节点数组值设置为其父节点的index，这样在推出时逆序压入堆栈，再重新打印出来，即可完成逆序打印工作。
有两个小点值得注意，一个是如果007非常牛逼，直接就可以跳出来的情况需要特殊处理一下。
二是按照题目要求，如果存在相同步数的路径，需要选出第一跳最短的那一条路径。为了实现这一功能，我在将鳄鱼节点录入时，先按照距离原点的距离升序排序。这样，在进行BFS的时候，总是先从短距离向长距离遍历，保证了第一跳最短距离的哪条路径最先被发现。
2.伪码实现
P = 007StartPoint;
if (Could Get Out at the StartPoint)
return FirstGetOut;
EnQueue(P,Queue)
while(IsNotEmpty(Queue))
{
P = DeQueue(Queue);
Find All the Point NextP that jump from P
{
if(NextP is not reached)
{
Jumped(NextP) = Jumped(P) + 1
father(NextP) = P
if(CouldGetOutFrom(NextP))
return NextP;
EnQueue(NextP, Queue)
}
}
}
return CouldNotJumpOut
3. 通过代码:
1 #define NONE -1 2 #define DISK 100000 3 #define MISTAKE -11 4 #define FIOUT 5000000 5 6 #include <stdio.h> 7 #include <stdlib.h> 8 9 10 11 static int jumped[101][101]; 12 13 void InitialJumped() 14 { 15 int i; 16 int j; 17 for(i=0;i<=100;i++) 18 { 19 for(j=0;j<=100;j++) 20 { 21 jumped[i][j]=NONE; 22 } 23 } 24 } 25 26 int IsJumped(int x,int y) 27 { 28 if(jumped[x+50][y+50] != NONE) 29 { 30 return 1; 31 } 32 else 33 { 34 return NONE; 35 } 36 } 37 38 void JumpOn(int x,int y,int jumpNum) 39 { 40 jumped[x+50][y+50]= jumpNum; 41 } 42 43 int GetJump(int x,int y) 44 { 45 return jumped[x+50][y+50]; 46 } 47 48 /////////End of Visited ///////////// 49 50 //////////Begin of Croc////////////// 51 52 typedef struct Croc{ 53 //location of this Croc 54 int x; 55 int y; 56 int dis; 57 }tCroc; 58 59 60 void SetDis(tCroc* C) 61 { 62 C->dis = (C->x)*(C->x) + (C->y)*(C->y); 63 } 64 65 int GetDis(tCroc* C) 66 { 67 return C->dis; 68 } 69 70 //If bond could reach from ori to des. 71 int Reachable(tCroc* ori,tCroc* des,int step) 72 { 73 int oriX; 74 int oriY; 75 int desX; 76 int desY; 77 int distanceSquare; 78 int stepSquare; 79 80 oriX = ori->x; 81 oriY = ori->y; 82 83 desX = des->x; 84 desY = des->y; 85 86 distanceSquare = (oriX-desX)*(oriX-desX)+(oriY-desY)*(oriY-desY); 87 stepSquare = step*step; 88 89 if(stepSquare >= distanceSquare) 90 { 91 return 1; 92 } 93 else 94 { 95 return 0; 96 } 97 } 98 99 100 int GetOut(tCroc *ori,int step)101 {102 if(ori->x + step >= 50)103 {104 return 1;105 }106 if(ori->x - step <= -50)107 {108 return 1;109 }110 if(ori->y + step >= 50)111 {112 return 1;113 }114 if(ori->y - step <= -50)115 {116 return 1;117 }118 return 0;119 }120 121 //////////End of Croc////////////////122 123 /////////DFS of Croc/////////////////124 125 int DFSofCroc(tCroc *ori,tCroc list[],int numOfCroc,int step)126 {127 int i;128 int localStep;129 130 JumpOn(ori->x,ori->y,1);131 132 if((ori->x == 0)&& (ori->y == 0))133 {134 localStep = step+8;135 }136 else137 {138 localStep = step;139 }140 141 142 if(GetOut(ori,localStep)==1)143 {144 return 1;145 }146 147 for(i = 0;i<numOfCroc;i++)148 {149 if(Reachable(ori,&list[i],localStep)==1)150 {151 if(IsJumped(list[i].x,list[i].y)==NONE)152 {153 int result;154 result = DFSofCroc(&list[i],list,numOfCroc,step);155 if(result == 1)156 {157 return 1;158 }159 }160 }161 }162 return 0;163 }164 //////////////////End of DFS Croc without COUNT/////////////////165 166 /////////////////Begin of queue//////////////167 168 typedef struct queueNode{169 tCroc * thisCroc;170 struct queueNode * nextCroc;171 }QNode;172 173 typedef struct CrocQueue{174 QNode *head;175 QNode *tail;176 }tCrocQueue;177 178 tCrocQueue* InitialQueue()179 {180 tCrocQueue* temp = malloc(sizeof(tCrocQueue));181 temp->head = NULL;182 temp->tail = NULL;183 return temp;184 }185 186 void EnQueue(QNode *node,tCrocQueue *Q)187 {188 if(Q->head == NULL)189 {190 Q->head = node;191 Q->tail = node;192 return ;193 }194 else195 {196 Q->tail->nextCroc = node;197 Q->tail = node;198 return;199 }200 }201 202 QNode * DeQueue(tCrocQueue *Q)203 {204 if(Q->head == NULL)205 {206 return NULL;207 }208 else209 {210 QNode *temp = Q->head;211 if(Q->head == Q->tail)212 {213 Q->head = NULL;214 Q->tail = NULL;215 }216 else217 {218 Q->head = Q->head->nextCroc;219 }220 return temp;221 }222 }223 224 int IsQueueEmpty(tCrocQueue *Q)225 {226 if(Q->head == NULL)227 {228 return 1;229 }230 else231 {232 return 0;233 }234 }235 ////////////////End of queue /////////////////236 237 ////////////////Begin of BFS/////////////////238 239 int BFS(tCroc *ori, tCroc list[], int Sum, int step, tCrocQueue *Q, int father[])240 {241 int count;242 int myfather;243 myfather = DISK;244 count = 0;245 JumpOn(ori->x,ori->y,count);246 if(GetOut(ori,step+8)==1)247 {248 return FIOUT;249 }250 QNode * thisNode = malloc(sizeof(QNode));251 thisNode->thisCroc = ori;252 EnQueue(thisNode,Q);253 while(IsQueueEmpty(Q)==0)254 {255 int i ;256 int localStep;257 QNode* temp = DeQueue(Q);258 259 count = GetJump(temp->thisCroc->x,temp->thisCroc->y);260 261 if((temp->thisCroc->x == 0)&&(temp->thisCroc->y==0))262 {263 localStep = step + 8;264 myfather = DISK;265 }266 else267 {268 localStep = step;269 for(i = 0; i < Sum ; i++)270 {271 if((temp->thisCroc->x == list[i].x)&&(temp->thisCroc->y== list[i].y))272 {273 myfather = i;274 break;275 }276 }277 }278 279 280 for(i = 0; i < Sum ;i++)281 {282 if(Reachable(temp->thisCroc,&list[i],localStep)==1)283 {284 if(IsJumped(list[i].x,list[i].y)==NONE)285 {286 JumpOn(list[i].x,list[i].y,(count+1));287 father[i] = myfather;288 289 if(GetOut(&list[i],step)==1)290 {291 return i;292 }293 thisNode = malloc(sizeof(QNode));294 thisNode->thisCroc = &list[i];295 EnQueue(thisNode,Q);296 }297 }298 }299 }300 301 return NONE;302 }303 304 305 306 307 308 ////////////////End of BFS///////////////////309 ////////////////Begin Stack//////////////////310 typedef struct stackNode{311 tCroc *thisNode;312 struct stackNode * next;313 }tStackNode;314 315 typedef struct CrocStack{316 tStackNode* Top;317 tStackNode* Bottom;318 }tCrocStack;319 320 tCrocStack* InitialStack()321 {322 tCrocStack * temp = malloc(sizeof(tCrocStack));323 temp->Top = NULL;324 temp->Bottom = NULL;325 return temp;326 }327 328 void Push(tStackNode *node,tCrocStack * S)329 {330 if(S->Top == NULL)331 {332 S->Top = node;333 S->Bottom = node;334 }335 else336 {337 node->next = S->Top;338 S->Top = node;339 }340 }341 342 tStackNode *Pop(tCrocStack *S)343 {344 if(S->Top == NULL)345 {346 return NULL;347 }348 else349 {350 tStackNode * temp = S->Top;351 if(S->Top == S->Bottom)352 {353 S->Bottom = NULL;354 S->Top = NULL;355 }356 else357 {358 S->Top = S->Top->next;359 }360 return temp;361 }362 }363 364 int IsStackEmpty(tCrocStack *S)365 {366 if(S->Top == NULL)367 {368 return 1;369 }370 else371 {372 return 0;373 }374 }375 /////////////////End of Stack////////////////376 377 378 379 380 381 int main()382 {383 int numOfCrocs;384 int step;385 int i;386 387 InitialJumped();388 scanf("%d %d",&numOfCrocs,&step);389 390 tCroc crocs[numOfCrocs];391 int preCro[numOfCrocs];392 393 394 //Put all the cordinates X,Y into array395 for(i=0;i<numOfCrocs;i++)396 {397 int j;398 int tempX;399 int tempY;400 scanf("%d %d",&tempX,&tempY);401 if( tempX > 50 || tempX< -50 || tempY > 50 || tempY < -50 )402 {403 i--;404 numOfCrocs--;405 continue;406 }407 crocs[i].x = tempX;408 crocs[i].y = tempY;409 SetDis(&crocs[i]);410 for(j=i-1;j>=0;j--)411 {412 if(crocs[j].x == crocs[i].x && crocs[j].y == crocs[i].y)413 {414 i--;415 numOfCrocs--;416 j=MISTAKE;417 break;418 }419 }420 if(j==MISTAKE)421 {422 continue;423 }424 425 for(j=i;j>0;j--)426 {427 if(GetDis(&crocs[j])<GetDis(&crocs[j-1]))428 {429 tCroc temp = crocs[j-1];430 crocs[j-1]=crocs[j];431 crocs[j]=temp;432 }433 else434 {435 break;436 }437 }438 preCro[i] = NONE;439 }440 441 // printf("---------------\n");442 // for(i=0;i<numOfCrocs;i++)443 // {444 // printf("%d %d %d\n",crocs[i].x,crocs[i].y,crocs[i].dis);445 // }446 // printf("---------------\n");447 448 tCroc *Zero = malloc(sizeof(tCroc));449 Zero->x = 0;450 Zero->y = 0;451 452 tCrocQueue * MyQueue = InitialQueue();453 454 int result;455 456 result = BFS(Zero,crocs,numOfCrocs,step,MyQueue,preCro);457 458 if(result == NONE)459 {460 printf("0");461 return 0;462 }463 else if(result == FIOUT)464 {465 printf("1");466 }467 else468 {469 int Dis = GetJump(crocs[result].x,crocs[result].y);470 printf("%d\n",Dis+1);471 }472 473 tCrocStack * MyStack = InitialStack();474 while(result != DISK)475 {476 tStackNode *temp = malloc(sizeof(tStackNode));477 temp->thisNode = &crocs[result];478 Push(temp,MyStack);479 result = preCro[result];480 }481 482 while(IsStackEmpty(MyStack)==0)483 {484 int printX;485 int printY;486 tStackNode *temp = Pop(MyStack);487 488 printX = temp->thisNode->x;489 printY = temp->thisNode->y;490 printf("%d %d\n",printX,printY);491 }492 493 // result = DFSofCroc(Zero,crocs,numOfCrocs,step);494 495 // if(result == 1)496 // {497 // printf("Yes");498 // }499 // else500 // {501 // printf("No");502 // }503 504 return 0;505 }
PAT Mooc datastructure 6-1