HDU1026 Ignatius and the Princess I

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn = 105;
 6 char mapp[maxn][maxn];
 7 int q[maxn*maxn*4][2]; //队列，刚开始没有乘以4，结果RE了
 8 //dp[i][j]表示走到坐标(i,j)时所用的时间
 9 //pre[x][y]存储当前点的前一个点在队列中的位置
10 int pre[maxn][maxn], dp[maxn][maxn], n, m, f, r, tmp, t;
11 int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
12 
13 void bfs()
14 {
15     f = 0, r = 1; //f为头指针，r为尾指针
16     q[0][0] = 0, q[0][1] = 0, dp[0][0] = 0;
17 
18     while(f != r)
19     {
20         int x = q[f][0], y = q[f][1];
21         tmp = f; //与32行对应
22         f ++; //出队列
23 
24         for(int i = 0; i < 4; i++)
25         {
26             int xx = x + dir[i][0];
27             int yy = y + dir[i][1];
28             int tt = dp[x][y] + 1;
29             if(xx < 0 || xx >= n || yy < 0 || yy >= m || mapp[xx][yy] == ‘X‘) continue;
30             //如果当前点之前到达过，并且所用的时间小于或等于当前点，进行下一次循环。
31             if(dp[xx][yy] != -1 && dp[xx][yy] <= tt) continue;
32             if(mapp[xx][yy] != ‘.‘) tt += mapp[xx][yy] - ‘0‘; //遇到怪兽，原地扁他
33             pre[xx][yy] = tmp, q[r][0] = xx, q[r][1] = yy, dp[xx][yy] = tt, r ++;
34         }
35     }
36     return ;
37 }
38 
39 int Print(int x,int y)
40 {
41     int k = pre[x][y];
42 
43     if(pre[x][y] == -1) return 0; //不能走，则返回；
44     Print(q[k][0], q[k][1]); //好好体会这里的递归。
45 
46     printf("%ds:(%d,%d)->(%d,%d)\n", t++, q[k][0], q[k][1], x, y);
47     if(mapp[x][y] != ‘.‘) //说明是怪兽，原地痛打
48     for(int i = 0; i < mapp[x][y] - ‘0‘; i++) //数字多大就打多久
49     printf("%ds:FIGHT AT (%d,%d)\n", t++, x, y);
50     return 0;
51 }
52 
53 int main()
54 {
55     while(~scanf("%d %d", &n, &m))
56     {
57         for(int i = 0; i < n; i++)
58         for(int j = 0; j < m; j++) scanf(" %c", &mapp[i][j]);
59 
60         memset(dp, -1, sizeof(dp)); //都初始化为没有访问过
61         memset(pre, -1, sizeof(pre));
62         bfs();
63         
64         //说明走不到这一点
65         if(dp[n-1][m-1] == -1) printf("God please help our poor hero.\n");
66         else
67         {
68             printf("It takes %d seconds to reach the target position,"
69                    " let me show you the way.\n", dp[n-1][m-1]);
70             t = 1;
71             Print(n - 1,m - 1); //打印路径。
72         }
73         printf("FINISH\n");
74     }
75     return 0;
76 }