题目倒是简单,只不过要记录走过的路径和输出时候的特别格式让人很纠结。我使用指针记录父节点的数据,当找到解答的时候就根据指针反向遍历整个路径,并将路径上得节点压入栈中。在输出位置依据格式出栈输出即可。
#include <queue> #include <stack> using namespace std; #include<stdio.h> #include <memory.h> #define N 105 char labyrinth[N][N]; int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; int visited[N][N]; struct Point { int row,col; int time; Point* parent; friend bool operator == (const Point& a,const Point& b) { return a.row==b.row&&a.col==b.col; } friend bool operator < (const struct Point& a,const struct Point& b) { return a.time>b.time; } }; Point endPoint,startPoint; stack<Point> pointStack; Point pathArray[N*N]; int bfs() { startPoint.col=startPoint.row=startPoint.time=0; priority_queue<Point> pointQueue; pointQueue.push(startPoint); int arrayLength=0; while(!pointQueue.empty()) { pathArray[arrayLength]=pointQueue.top(); pointQueue.pop(); for (int i=0;i<4;i++) { int row=pathArray[arrayLength].row+dir[i][0]; int col=pathArray[arrayLength].col+dir[i][1]; if(row>endPoint.row||col>endPoint.col||row<0||col<0|| visited[row][col]||labyrinth[row][col]=='X') continue; visited[row][col]=true; Point newPoint; newPoint.row=row; newPoint.col=col; newPoint.time=pathArray[arrayLength].time+1; if(labyrinth[row][col]!='.') newPoint.time+=(labyrinth[row][col]-'0'); newPoint.parent=&pathArray[arrayLength]; if(newPoint==endPoint) { //延迟时间,存入栈中 Point* parent=&newPoint; while(parent!=NULL) { pointStack.push(*parent); parent=parent->parent; } return newPoint.time; } pointQueue.push(newPoint); } arrayLength++; } return 0; } int main() { //freopen("Ignatius and the Princess I.txt","r",stdin); while(scanf("%d%d",&(endPoint.row),&(endPoint.col))!=EOF) { endPoint.row--; endPoint.col--; getchar(); for (int i=0;i<=endPoint.row;i++) gets(labyrinth[i]); memset(visited,0,sizeof(visited)); int timeCnt=bfs(); if(timeCnt) { printf("It takes %d seconds to reach the target position, let me show you the way.\n",timeCnt); for (int i=1,cnt=1;cnt<=timeCnt;cnt++,i++) { Point tempPoint=pointStack.top(); pointStack.pop(); Point currentPoint=pointStack.top(); printf("%ds:(%d,%d)->(%d,%d)\n",cnt,tempPoint.row,tempPoint.col,currentPoint.row,currentPoint.col); char a=labyrinth[currentPoint.row][currentPoint.col]; if(a!='.') for (int k=0;k<a-'0';k++) { cnt++; printf("%ds:FIGHT AT (%d,%d)\n",cnt,currentPoint.row,currentPoint.col); } } pointStack.pop(); } else printf("God please help our poor hero.\n"); printf("FINISH\n"); } return 0; }