HDU1026 Ignatius and the Princess I

解题思路:打印路径是关键,细节处理见代码。

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = ;
char mapp[maxn][maxn];
int q[maxn*maxn*][]; //队列,刚开始没有乘以4,结果RE了
//dp[i][j]表示走到坐标(i,j)时所用的时间
//pre[x][y]存储当前点的前一个点在队列中的位置
int pre[maxn][maxn], dp[maxn][maxn], n, m, f, r, tmp, t;
int dir[][] = {, , -, , , , , -}; void bfs()
{
f = , r = ; //f为头指针,r为尾指针
q[][] = , q[][] = , dp[][] = ; while(f != r)
{
int x = q[f][], y = q[f][];
tmp = f; //与32行对应
f ++; //出队列 for(int i = ; i < ; i++)
{
int xx = x + dir[i][];
int yy = y + dir[i][];
int tt = dp[x][y] + ;
if(xx < || xx >= n || yy < || yy >= m || mapp[xx][yy] == 'X') continue;
//如果当前点之前到达过,并且所用的时间小于或等于当前点,进行下一次循环。
if(dp[xx][yy] != - && dp[xx][yy] <= tt) continue;
if(mapp[xx][yy] != '.') tt += mapp[xx][yy] - ''; //遇到怪兽,原地扁他
pre[xx][yy] = tmp, q[r][] = xx, q[r][] = yy, dp[xx][yy] = tt, r ++;
}
}
return ;
} int Print(int x,int y)
{
int k = pre[x][y]; if(pre[x][y] == -) return ; //不能走,则返回;
Print(q[k][], q[k][]); //好好体会这里的递归。 printf("%ds:(%d,%d)->(%d,%d)\n", t++, q[k][], q[k][], x, y);
if(mapp[x][y] != '.') //说明是怪兽,原地痛打
for(int i = ; i < mapp[x][y] - ''; i++) //数字多大就打多久
printf("%ds:FIGHT AT (%d,%d)\n", t++, x, y);
return ;
} int main()
{
while(~scanf("%d %d", &n, &m))
{
for(int i = ; i < n; i++)
for(int j = ; j < m; j++) scanf(" %c", &mapp[i][j]); memset(dp, -, sizeof(dp)); //都初始化为没有访问过
memset(pre, -, sizeof(pre));
bfs(); //说明走不到这一点
if(dp[n-][m-] == -) printf("God please help our poor hero.\n");
else
{
printf("It takes %d seconds to reach the target position,"
" let me show you the way.\n", dp[n-][m-]);
t = ;
Print(n - ,m - ); //打印路径。
}
printf("FINISH\n");
}
return ;
}
上一篇:DP Codeforces Round #FF (Div. 1) A. DZY Loves Sequences


下一篇:dp - Codeforces Round #313 (Div. 1) C. Gerald and Giant Chess