HDU1026 Ignatius and the Princess I bfs（需要记录路径）

一开始用递归显示路径会爆栈，后来用数组road[]保存路径就过了
 1 #include<stdio.h>
 2 #include<queue>
 3 #include<string.h>
 4 using namespace std;
 5 int n,m;
 6 char map[110][110],hp[110][110],flag[110][110];
 7 int road[10010][2];
 8 int dir[4][2]={1,0,-1,0,0,1,0,-1};
 9 struct node
10 {
11     int x,y,step;
12     friend bool operator<(node a,node b)
13     {
14         return a.step>b.step;       
15     }       
16 }cur,next;
17 int bfs()
18 {
19     priority_queue<node>q;
20     cur.x=0;
21     cur.y=0;
22     cur.step=hp[0][0];
23     map[0][0]='X';
24     q.push(cur);
25     while(!q.empty())
26     {
27         cur=q.top();
28         q.pop();
29         if(cur.x==n-1&&cur.y==m-1) return 1;
30         for(int i=0;i<4;i++)
31         {
32             next.x=cur.x+dir[i][0];
33             next.y=cur.y+dir[i][1];
34             if(next.x<0||next.y<0||next.x>=n||next.y>=m||map[next.x][next.y]=='X') continue;
35             map[next.x][next.y]='X';
36             next.step=cur.step+hp[next.x][next.y]+1; 
37             flag[next.x][next.y]=i;
38             q.push(next);      
39         }                     
40     }  
41     return 0;  
42 }
43 int print()
44 {
45     road[cur.step][0]=n-1;
46     road[cur.step][1]=m-1;
47     int x,y;
48     int temp=cur.step;
49     cur.step-=hp[n-1][m-1];
50     road[cur.step][0]=n-1;
51     road[cur.step][1]=m-1;
52     while(!(cur.x==0&&cur.y==0))
53     {
54         x=cur.x-dir[flag[cur.x][cur.y]][0];
55         y=cur.y-dir[flag[cur.x][cur.y]][1]; 
56         road[cur.step-1][0]=x;
57         road[cur.step-1][1]=y;
58         cur.step-=hp[x][y]+1;
59         road[cur.step][0]=x;
60         road[cur.step][1]=y;
61         cur.x=x;
62         cur.y=y;  
63     }
64     for(int i=0;i<=temp-1;i++)
65     {
66         int k=i;
67         printf("%ds:(%d,%d)->(%d,%d)
",i+1,road[i][0],road[i][1],road[i+1][0],road[i+1][1]);            
68         while(hp[road[k+1][0]][road[k+1][1]]--)  
69         {
70             i++;
71             printf("%ds:FIGHT AT (%d,%d)
",i+1,road[k+1][0],road[k+1][1]); 
72         }
73     }
74     return 0;
75 }
76 int main()
77 {
78     while(scanf("%d%d",&n,&m)!=EOF)
79     {
80         memset(map,'X',sizeof(map));
81         memset(hp,0,sizeof(hp));
82         memset(flag,0,sizeof(flag));
83         memset(road,0,sizeof(road));
84         for(int i=0;i<n;i++)
85         {
86             scanf("%s",&map[i]); 
87             for(int j=0;j<m;j++)
88                 if(map[i][j]!='X'&&map[i][j]!='.') hp[i][j]=map[i][j]-'0';               
89         }
90         if(bfs())
91         {
92            printf("It takes %d seconds to reach the target position, let me show you the way.
",cur.step); 
93            print();        
94         }   
95         else printf("God please help our poor hero.
");
96         printf("FINISH
");                            
97     }
98 }