频道栏目
首页 > 考试 > 其他 > 正文

HDU1026 Ignatius and the Princess I

2016-08-17 09:43:59         来源:海岛Blog  
收藏   我要投稿

问题链接HDU1026 Ignatius and the Princess I

题意简述:从矩阵的左上角走到右下角所需的最短时间,并且要求输出走的过程。矩阵中"."是可以走的,"X"是墙,n(数字1-9)是怪兽,需要战斗数字所示的时间。对于每个测试实例,先输入n和m,分别表示行数和列数,然后输入矩阵。

问题分析:显然求最短路径问题用BFS,另外由于有怪兽,所以搜索过程需要使用优先队列。一个典型的用分支限界法解决的问题。最小路径上每个点到出发点距离应该是最小的。

程序说明:用节点矩阵grid[][]存储输入的矩阵,同时存储输入的矩阵和到起始点需要行走的最少步骤,以及最小路径上前一个节点坐标。这个程序运行时间上算是比较短的。

AC的C++语言程序如下:

 

/* HDU1026 Ignatius and the Princess I */

#include 
#include 
#include 
#include 
#include 

using namespace std;

#define DIRECTSIZE 4

struct direct {
    int drow;
    int dcol;
} direct[DIRECTSIZE] =
    {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

const int MAXN = 100;
const unsigned int MAXTIME = MAXN*MAXN*9+1;

struct gridnode {
    char v;
    int prevrow, prevcol;
    unsigned int mintime;
};

gridnode grid[MAXN+1][MAXN+1];

struct node {
    int row, col;
    unsigned int sumtime;

    bool operator<(const node n) const {
        return sumtime > n.sumtime;
    }
};

int n, m;
unsigned int mintime;
node start, end2, f, v;

int bfs()
{
    int ans = 0;

    grid[0][0].prevrow = -1;
    grid[0][0].prevcol = -1;
    grid[0][0].mintime = 0;

    start.row = 0;
    start.col = 0;
    start.sumtime = 0;

    end2.row = n - 1;
    end2.col = m - 1;

    mintime = MAXTIME;

    priority_queue q;
    q.push(start);

    while(!q.empty()) {
        f = q.top();
        q.pop();

        if(f.row == end2.row && f.col == end2.col) {
            if(f.sumtime < mintime) {
                mintime = f.sumtime;
                ans = 1;
                continue;
            }
        }

        if(f.sumtime >= mintime)
            continue;

        for(int i=0; i s;
    node v1, v2;

    v.row = end2.row;
    v.col = end2.col;
    s.push(v);
    while(grid[v.row][v.col].prevrow != -1 || grid[v.row][v.col].prevcol != -1) {
        v2 = v;
        v.row = grid[v2.row][v2.col].prevrow;
        v.col = grid[v2.row][v2.col].prevcol;
        s.push(v);
    }


    printf("It takes %d seconds to reach the target position, let me show you the way.\n", mintime);

    int count = 0;
    v1 = s.top();
    s.pop();
    while(!s.empty()) {
        v2 = s.top();
        s.pop();
        printf("%ds:(%d,%d)->(%d,%d)\n", ++count, v1.row, v1.col, v2.row, v2.col);
        if(grid[v2.row][v2.col].v != '.') {
            for(int j=1; j<=grid[v2.row][v2.col].v-'0'; j++)
                printf("%ds:FIGHT AT (%d,%d)\n", ++count, v2.row, v2.col);
        }

        v1 = v2;
    }
}

char mygetchar()
{
    char c;

    while((c = getchar()) && (c == ' ' || c == '\t' || c == '\n'));

    return c;
}

int main()
{
    while(scanf("%d%d", &n, &m) != EOF) {
        for(int i=0; i

 

相关TAG标签
上一篇:2013年福建省程序设计竞赛省赛题解
下一篇:UVA494 Kindergarten Counting Game
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站