hdu 1026【Ignatius and the Princess I】

广搜
我用path记录路径，初始为-1，并且可以用path标记该点是否走过，如果为-1则表示没有走过，一举两得，然后用print递归输出路径。在记录路径时我是将点的坐标转化为一个数值即X*M+Y，当输出路径的时候可将path里面的值转化为坐标……
代码如下：
  1 #include <iostream>
  2 #include <queue>
  3 #include <cstdio>
  4 using namespace std;
  5 
  6 const int maxlen = 100 + 10;
  7 struct place 
  8 {
  9     int x,y;
 10     int step;
 11     friend bool operator <(place a,place b)
 12     {
 13         return a.step > b.step;
 14     }
 15 };
 16 int path[maxlen][maxlen];
 17 char map[maxlen][maxlen];
 18 int N,M;
 19 int dirx[4] = {-1,0,1,0};
 20 int diry[4] = {0,-1,0,1};
 21 
 22 int bfs()
 23 {
 24     priority_queue<place> q;
 25     place Start;
 26     Start.x = 0;
 27     Start.y = 0;
 28     Start.step = 0;
 29     q.push(Start);
 30     path[0][0] = 0;
 31     while(!q.empty())
 32     {
 33         place temp = q.top();
 34         q.pop();
 35         if(temp.x == N - 1 &&temp.y == M -1)
 36         {
 37             return temp.step;
 38         }
 39 
 40         place tmp;
 41         for(int i = 0;i < 4;i ++)
 42         {
 43             int rx = temp.x + dirx[i];
 44             int ry = temp.y + diry[i];
 45             if(rx < 0 || rx >= N || ry < 0 || ry >= M)
 46                 continue;
 47 
 48             if(map[rx][ry] == '.'&&path[rx][ry] == -1)
 49             {
 50                 tmp.x = rx;
 51                 tmp.y = ry;
 52                 tmp.step = temp.step + 1;
 53                 path[rx][ry] = temp.x * M + temp.y;
 54                 q.push(tmp);
 55             }
 56             if(map[rx][ry] != '.'&&map[rx][ry] != 'X' && path[rx][ry] == -1)
 57             {
 58                 tmp.x = rx;
 59                 tmp.y = ry;
 60                 int num = map[rx][ry] - '0';
 61                 tmp.step = temp.step + num + 1;
 62                 path[rx][ry] = temp.x * M + temp.y;
 63                 q.push(tmp);
 64             }
 65         }
 66 
 67     }
 68 
 69     return -1;
 70 }
 71 
 72 void print(int x,int y,int s)
 73 {
 74     if(x == 0 && y == 0)
 75     {
 76         //cout << s <<"s:(0,0)->";
 77         return;
 78     }
 79     int rx = path[x][y] / M;
 80     int ry = path[x][y] % M;
 81     if(map[x][y] != '.' && map[x][y] != 'X')
 82     {
 83         int num = map[x][y] - '0';
 84         print(rx,ry,s - num - 1);
 85         cout << s-num << "s:(" << rx << "," << ry <<")->";
 86         cout << "(" <<x << "," <<y <<")" <<endl;
 87         for(int i = 0;i < num;i ++)
 88         {
 89         cout << s -num +1+i <<"s:FIGHT AT (" <<x <<","<<y <<")" << endl;
 90         }
 91     }
 92     else if(map[x][y] == '.')
 93     {
 94         print(rx,ry,s-1);
 95         cout << s << "s:(" << rx << "," << ry <<")->";
 96         cout << "(" <<x << "," <<y <<")" <<endl;
 97     }
 98 }
 99 
100             
101 int main()
102 {
103     while(cin >> N >> M)
104     {
105         memset(path,-1,sizeof(path));
106         for(int i = 0;i < N;i ++)
107         {
108             for(int j = 0;j < M;j ++)
109             {
110                 cin >> map[i][j];
111             }
112         }
113 
114         int ans = bfs();
115         if(ans == -1)
116         {
117             cout << "God please help our poor hero." << endl;
118         }
119         else
120         {
121             cout << "It takes " << ans << " seconds to reach the target position, let me show you the way." << endl;
122             print(N-1,M-1,ans);
123         }
124         cout << "FINISH" << endl;
125     }
126 
127     return 0;
128 }