hdu

http://acm.hdu.edu.cn/showproblem.php?pid=1026

求起点到终点的最少花费，输出路径的时候麻烦一点，借鉴了别人的思路，用dfs 递归打印出路径。

用额外一个二维数组标记当前点的前驱，因为点是一个坐标，那么可以用 s=x*m+y 映射成一个点就可以了。

这样知道这个数值在求出坐标的话，x=s/m,y=s%m。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cmath>
  4 #include <vector>
  5 #include <cstring>
  6 #include <string>
  7 #include <algorithm>
  8 #include <string>
  9 #include <set>
 10 #include <functional>
 11 #include <numeric>
 12 #include <sstream>
 13 #include <stack>
 14 #include <map>
 15 #include <queue>
 16 #pragma comment(linker, "/STACK:102400000,102400000")
 17 #define CL(arr, val)    memset(arr, val, sizeof(arr))
 18 
 19 #define ll long long
 20 #define inf 0x7f7f7f7f
 21 #define lc l,m,rt<<1
 22 #define rc m + 1,r,rt<<1|1
 23 #define pi acos(-1.0)
 24 
 25 #define L(x)    (x) << 1
 26 #define R(x)    (x) << 1 | 1
 27 #define MID(l, r)   (l + r) >> 1
 28 #define Min(x, y)   (x) < (y) ? (x) : (y)
 29 #define Max(x, y)   (x) < (y) ? (y) : (x)
 30 #define E(x)        (1 << (x))
 31 #define iabs(x)     (x) < 0 ? -(x) : (x)
 32 #define OUT(x)  printf("%I64d
", x)
 33 #define lowbit(x)   (x)&(-x)
 34 #define Read()  freopen("a.txt", "r", stdin)
 35 #define Write() freopen("b.txt", "w", stdout);
 36 #define maxn 1000000000
 37 #define N 2510
 38 #define mod 1000000000
 39 using namespace std;
 40 
 41 char field[110][110];
 42 int used[110][110];
 43 int n,m,time;
 44 int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
 45 struct point
 46 {
 47     int x,y,step;
 48     bool operator < (const point a) const
 49     {
 50         return step>a.step;
 51     }
 52 };
 53 int bfs()
 54 {
 55     point s;
 56     s.x=0,s.y=0,s.step=0;
 57     priority_queue<point>que;
 58     que.push(s);
 59     while(!que.empty())
 60     {
 61         point e=que.top();
 62         que.pop();
 63         if(e.x==n-1&&e.y==m-1) return e.step;
 64         for(int i=0;i<4;i++)
 65         {
 66             s=e;
 67             s.x=e.x+dir[i][0];
 68             s.y=e.y+dir[i][1];
 69             if(s.x>=0&&s.x<n&&s.y>=0&&s.y<m&&field[s.x][s.y]!='X'&&used[s.x][s.y]==-1)
 70             {
 71                 used[s.x][s.y]=e.x*m+e.y;
 72                 s.step+=1;
 73                 char c=field[s.x][s.y];
 74                 if(c>='0'&&c<='9') s.step+=c-'0';
 75                 //printf("%d %d %d
",e.x,e.y,e.step);
 76                 que.push(s);
 77             }
 78         }
 79     }
 80     return 0;
 81 }
 82 
 83 void get_path(int x,int y)
 84 {
 85     if(x==0&&y==0) return;
 86    // printf("%d
",used[x][y]);
 87     int a=used[x][y]/m,b=used[x][y]%m;
 88     get_path(a,b);
 89     printf("%ds:(%d,%d)->(%d,%d)
",time++,a,b,x,y);
 90     if(field[x][y]>='0'&&field[x][y]<='9')
 91     {
 92         while(field[x][y]>'0')
 93         {
 94             printf("%ds:FIGHT AT (%d,%d)
",time++,x,y);
 95             field[x][y]--;
 96         }
 97     }
 98 }
 99 int main()
100 {
101    // freopen("a.txt","r",stdin);
102     while(~scanf("%d%d",&n,&m))
103     {
104         getchar();
105         for(int i=0;i<n;i++)
106         {
107             scanf("%s",field[i]);
108         }
109         memset(used,-1,sizeof(used));
110         int flag=bfs();
111         if(flag)
112         {
113             printf("It takes %d seconds to reach the target position, let me show you the way.
",flag);
114             time=1;
115             get_path(n-1,m-1);
116         }
117         else printf("God please help our poor hero.
");
118         printf("FINISH
");
119     }
120     return 0;
121 }