HDU 1026 Ignatius and the Princess I(优先队列bfs) - dblank

HDU 1026 Ignatius and the Princess I(优先队列bfs)

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1026;

题意:给你一个地图,上面有障碍和怪兽,障碍不可以走,怪兽有hp值,每点hp有消耗一秒时间去攻击,起点在(0,0),终点在

(n-1, m-1),还要把路径输出.

#include<iostream>  
#include<algorithm>  
#include<map>  
#include<cstring>  
#include<queue>  
#include<set>  
#include<cstdio>  
#include<cmath>  
#include<stack>  
using namespace std;  
int n, m, run[][2] = {1, 0, 0, 1, -1, 0, 0, -1};  
const int N = 1e2 + 17;  
int vis[N][N];  
struct node  
{  
    int x, y, t;  
    bool operator < (const node &a) const //重载小于号运算符  
    {  
        return t > a.t;  
    }  
};  
node root[N][N];//前驱节点  
char Map[N][N];  
bool yes(node a)  
{  
    if(a.x<0||a.x>n-1||a.y<0||a.y>m-1||Map[a.x][a.y] == 'X'||vis[a.x][a.y])  
        return false;  
    return true;  
}  
int bfs()  
{  
    for(int i = 0; i < n; i ++)  
        for(int j = 0; j < m; j ++)  
            root[i][j].x = root[i][j].y = root[i][j].t = -1;  
    priority_queue<node>q;  
    node in, out;  
    in.x = 0, in.y = 0, in.t = 0;  
    if(Map[0][0]>='0' && Map[0][0]<='9')  
        in.t = Map[0][0] - '0';  
    root[0][0].x = -1 , root[0][0].y = -1;  
    q.push(in);  
    vis[0][0] = 1;  
    while(!q.empty())  
    {  
        in = q.top();  
        q.pop();  
        if(in.x == n-1 && in.y == m-1)  
        {  
            return in.t;  
        }  
        for(int i = 0; i<4; i++)  
        {  
            out.x = in.x + run[i][0];  
            out.y = in.y + run[i][1];  
            if(yes(out))  
            {  
                if(isdigit(Map[out.x][out.y]))  
                    out.t = Map[out.x][out.y] - '0' + in.t + 1;  
                else  
                    out.t = in.t + 1;  
                vis[out.x][out.y] = 1;  
                root[out.x][out.y] = in;  
                root[out.x][out.y].t = out.t;  
                q.push(out);  
            }  
        }  
    }  
    return 0;  
}  
int main()  
{  
    while(~scanf("%d%d", &n, &m))  
    {  
        memset(vis, 0, sizeof(vis));  
        for(int i = 0; i<n; i++)  
            for(int j = 0; j<m; j++)  
                scanf(" %c", &Map[i][j]);  
        int ok = bfs();  
        if(!ok)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", ok);  
            node r;  
            r.x = n-1, r.y = m-1;  
            stack<node>st;//用一个栈来保存路径  
            while(root[r.x][r.y].x!= -1 || root[r.x][r.y].y != -1)  
            {  
                st.push(r);  
                r = root[r.x][r.y];  
            }  
            node shit;  
            int t = 1;  
            shit = st.top();  
            if(isdigit(Map[0][0]))  
                for(int i = 1; i<=Map[0][0] - '0'; i++)  
                    printf("%ds:FIGHT AT (0,0)\n", t++);  
            while(st.size())  
            {  
                shit = st.top();  
                st.pop();  
                node cc = root[shit.x][shit.y];  
                printf("%ds:(%d,%d)->(%d,%d)\n", t++, cc.x, cc.y, shit.x, shit.y);  
                if(isdigit(Map[shit.x][shit.y]))  
                {  
                    int fuck = Map[shit.x][shit.y] - '0';  
                    for(int i = 1; i<=fuck; i++)  
                        printf("%ds:FIGHT AT (%d,%d)\n", t++, shit.x, shit.y);  
                }  
            }  
        }  
        printf("FINISH\n");  
    }  
    return 0;  
}

 

相关文章

仅有 1 条评论
  1. Direct Lender Loans

    no fax payday loans direct lenders online loans instant approval no credit check payday loans instant approval online loans instant approval

    Direct Lender Loans 回复
发表新评论