本文共 4460 字,大约阅读时间需要 14 分钟。
5 6.XX.1...X.2.2...X....XX.XXXXX.5 6.XX.1...X.2.2...X....XX.XXXXX15 6.XX.....XX1.2...X....XX.XXXXX.
It takes 13 seconds to reach the target position, let me show you the way.1s:(0,0)->(1,0)2s:(1,0)->(1,1)3s:(1,1)->(2,1)4s:(2,1)->(2,2)5s:(2,2)->(2,3)6s:(2,3)->(1,3)7s:(1,3)->(1,4)8s:FIGHT AT (1,4)9s:FIGHT AT (1,4)10s:(1,4)->(1,5)11s:(1,5)->(2,5)12s:(2,5)->(3,5)13s:(3,5)->(4,5)FINISHIt takes 14 seconds to reach the target position, let me show you the way.1s:(0,0)->(1,0)2s:(1,0)->(1,1)3s:(1,1)->(2,1)4s:(2,1)->(2,2)5s:(2,2)->(2,3)6s:(2,3)->(1,3)7s:(1,3)->(1,4)8s:FIGHT AT (1,4)9s:FIGHT AT (1,4)10s:(1,4)->(1,5)11s:(1,5)->(2,5)12s:(2,5)->(3,5)13s:(3,5)->(4,5)14s:FIGHT AT (4,5)FINISHGod please help our poor hero.FINISH //要队列优先 因为每个点并不是1 所以wa了 //我的第一次这种做法是为了记录路径 用STL队列保存路径感觉好麻烦 //改进后AC 用数组加快排模拟优先队列 #include#include #include #include #include using namespace std;const int N=100+5;int map[N][N];int n,m,goal;bool ok;int route[N*N];bool book[N][N];struct Node{ int x,y; int last; int step;}node,tmp;Node q[N*N];int step[4][2]={ {0,1},{1,0},{-1,0},{0,-1}};bool cmp(Node a,Node b){ return a.step<=b.step;}int main(){ int i,j,head,tail; char c[N]; while(scanf("%d%d",&n,&m)==2){ head=0; tail=0; ok=0; for(i=0;i ='1'&&c[j]<='9') map[i][j]=c[j]-'0'+1; else map[i][j]=-1; } } book[0][0]=1; node.last=0; node.x=0; node.y=0; node.step=0; q[tail++]=node; while(head =n||b<0||b>=m||map[a][b]==-1||book[a][b]==1) continue; book[a][b]=1; node.x=a; node.y=b; node.last=head; node.step=tmp.step+map[a][b]; q[tail++]=node; } // book[tmp.x][tmp.y]=0; head++; } if(ok) {printf("It takes %d seconds to reach the target position, let me show you the way.\n",q[goal].step); i=0,j=goal; while(j!=0){ //处理路径 route[i++]=j; j=q[j].last; } route[i]=0; //路径最开始是head=0 for(j=1;i>=0;i--,j++){ int a=q[route[i]].x; int b=q[route[i]].y; if(map[a][b]>1){ while(map[a][b]>1){ printf("%ds:FIGHT AT (%d,%d)\n",j,a,b); j++; map[a][b]--; } } if(i>0) printf("%ds:(%d,%d)->(%d,%d)\n",j,a,b,q[route[i-1]].x,q[route[i-1]].y); } } else printf("God please help our poor hero.\n"); printf("FINISH\n"); } return 0;}
转载地址:http://xymvi.baihongyu.com/