HDU1026(bfs+优先级队列)

题目链接

传送门

题目大意

题意可以抽象为一个n * m矩阵,左上角(0 , 0)为入口,右下角(n-1 , m-1)为出口,’.’代表格子能走,’X’代表格子不能走, ‘n’代表走过当前格子需要消耗n秒时间,问是否能通过迷宫。如果能,那么请输出总共时间,并把路径输出。

解题思路

首先开一个结构体pre来保存走过的路径,vis标记是否走过。每次向四个方向广搜,如果下标不越界+没被标记+不是’X’,那 么就可以走。如果是’.’的话,记录下它的前驱,时间+1;如果是’n’,那么记录前驱时时间依据n值而定。最后如果搜到右下角(n-1,m-1)时,返回输出。注:bfs刚开 始时要清空队列。 输出时递归输出。

参考代码

#include <functional>  
#include <algorithm>  
#include <iostream>  
#include <fstream>  
#include <sstream>  
#include <iomanip>  
#include <numeric>  
#include <cstring>  
#include <climits>  
#include <cassert>  
#include <complex>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <bitset>  
#include <queue>  
#include <stack>  
#include <cmath>  
#include <ctime>  
#include <list>  
#include <set>  
#include <map>  
using namespace std;  

#pragma comment(linker, "/STACK:102400000,102400000")  

typedef long long LL;  
typedef double DB;  
typedef unsigned uint;  
typedef unsigned long long uLL;  

/** Constant List .. **/ //{  

const int MOD = int(1e9)+7;  
const int INF = 0x3f3f3f3f;  
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;  
const DB EPS = 1e-9;  
const DB OO = 1e20;  
const DB PI = acos(-1.0); //M_PI;  

struct node  
{  
    int x;  
    int y;  
    int time;  
    friend bool operator < (node a , node b)  
    {  
        return a.time > b.time;  
    }  
}pre[1111][1111];  

char maps[1111][1111];  
int vis[1111][1111];  
int d[4][2] = {-1 , 0 , 0 , 1 , 1 , 0 , 0 , -1};  
int step;  
int n , m;  
priority_queue<node> q;  

void bfs()  
{  
    while(!q.empty())  
        q.pop();  
    node t1 , t2;  
    t1.x = 0;  
    t1.y = 0;  
    t1.time = 0;  
    pre[0][0].x = -1;  
    pre[0][0].y = -1;  
    pre[0][0].time = 0;  
    q.push(t1);  
    while(!q.empty())  
    {  
        t1 = q.top();  
        q.pop();  
        for(int i = 0 ; i < 4 ; i ++)  
        {  
            t2.x = d[i][0] + t1.x;  
            t2.y = d[i][1] + t1.y;  
            if(t2.x >= 0 && t2.x < n && t2.y >= 0 && t2.y < m && !vis[t2.x][t2.y] && maps[t2.x][t2.y] != 'X')  
            {  
                if(maps[t2.x][t2.y] == '.')  
                {  
                    t2.time = t1.time + 1;  
                    pre[t2.x][t2.y].x = t1.x;  
                    pre[t2.x][t2.y].y = t1.y;  
                    pre[t2.x][t2.y].time = 0;  
                    vis[t2.x][t2.y] = 1;  
                    q.push(t2);  
                }  
                else if(maps[t2.x][t2.y] >= '1' && maps[t2.x][t2.y] <= '9')  
                {  
                    t2.time = t1.time + (maps[t2.x][t2.y] - '0') + 1;  
                    pre[t2.x][t2.y].x = t1.x;  
                    pre[t2.x][t2.y].y = t1.y;  
                    pre[t2.x][t2.y].time = maps[t2.x][t2.y] - '0';  
                    vis[t2.x][t2.y] = 1;  
                    q.push(t2);  
                }  
                if(t2.x == n - 1 && t2.y == m - 1)  
                {  
                    step = t2.time;  
                    printf("It takes %d seconds to reach the target position, let me show you the way.\n" , step);  
                    return;  
                }  
            }  
        }  
    }  
}  

void path(int x , int y , int len)  
{  
    if(len > 0)  
    {  
        if(pre[x][y].time -- != 0 )  
        {  
            path(x , y , len -  1);  
            printf("%ds:FIGHT AT (%d,%d)\n", len , x , y);  
        }  
        else  
        {  
            path(pre[x][y].x , pre[x][y].y , len - 1);  
            printf("%ds:(%d,%d)->(%d,%d)\n" , len , pre[x][y].x , pre[x][y].y , x , y);  
        }  
    }  
}  

int main()  
{  
    #ifdef DoubleQ  
    freopen("in.txt","r",stdin);  
    #endif  

    while(~scanf("%d%d",&n,&m))  
    {  
        for(int i = 0 ; i < n ; i ++)  
            scanf("%s",maps[i]);  
        step = -1;  
        memset(vis , 0 , sizeof(vis));  
        vis[0][0] = 1;  
        bfs();  
        if(step == -1)  
        {  
            printf("God please help our poor hero.\nFINISH\n");  
            continue;  
        }  
        path(n - 1 , m - 1 , step);  
        printf("FINISH\n");  
    }  
}  

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

© 2018-2019 惜春令 京ICP备18010644号 网站地图