Question

一道超难的c语言迷宫问题

Judge Info
Memory Limit: 65536KB
Case Time Limit: 1000MS
Time Limit: 1000MS
Judger: Normal
Description
主人公仙石晃与同学们一起参加学校毕业旅行，但在回程的途中遭遇空难。主人公和同伴们被迫滞留在一个未知的小岛、蛮荒世界里。主人公和同伴们抱着种种疑问在这个弱肉强食、危机四伏的世界里挣扎求存。 为了简化问题，可以将整个小岛看成一个N * M的方格矩阵，每个方格里有一个整数，正数时表示主人公带领同伴离开该方格地型所需花费的时间（忽略进入方格所需时间），负数时表示该方格地型是障碍物，不可进入。很不幸，在其中一些方格里徘徊着一些凶猛上古猛兽，猛兽都拥有敏锐的臭觉，每个猛兽都有一个搜寻猎物能力值bi, 当有猎物出现其所在的方格地型里，猛兽就会穷追不舍，直到发现猎物，并瞬间吞杀所有猎物。初始时主人公与同伴在方格(1,1)里，只能往上下左右四个方向移动，如果途中移动到有猛兽的格子里，则会被这个猛兽追踪，在以后移动到的每个格子(包括该猛兽初始所在格子)里停留的时间不能超过K-sumB, K为一个整数常量，sumB为当前追踪主人公团队的所有猛兽的能力值总和。在方格(N,M)里有个安全的避难所，主人公要在最短的时间内带领同伴们安全抵达避难所,进入安全区域后不会受到攻击，并且避难所所在方格保证不为障碍物。
Input
输入只有一组数据。 第一行输入两个整数N,M (0 < N, M < 100)。 接下来N行，每行有M个以空格分开的整数，每个整数的绝对值不超过1000。 接下来一行输入两个整数L, K（0 <= L <= 5， 0 <= K <= 1000)，L表示该小岛上猛兽的个数,K为题意所示的整数常量。 接下来L行，每行三个整数xi,yi,bi, (1<=xi<=N, 1<=yi<=M, 0<=bi<=1000)，(xi, yi)表示第i个猛兽初始时所在的方格为第xi行、yi列，bi表示第i个猛兽的搜寻猎物能力值。初始时保证同一个方格不会出现多于一个猛兽，并且猛兽在没有发现猎物之前会一直停留在这个方格里。
Output
如果主人公仙石晃能安全抵达避难所，输出其到达避难所所用的最短时间。 否则，输出一行"Oh~,poor boys and girls!"，不包括双引号。
Sample Input
4 4
7 9 8 1
5 7 7 10
8 -10 -7 5
10 4 4 3
2 8
2 1 2
3 4 1
Sample Output
40

Answer 1

没觉得多难……三维数组的BFS而已。

话说出题人是《逃离伊甸园》看多了吗？

PS：请题主提供题目的链接。

//
//   File name      : Main.cpp
//
//   Code by        : jiangyonghang
//
//   Project name   : EscapeFromEden
//
//   Create datetime: 2014-02-15 09:06:28
//

// Tested or implemented header
// ...

// C system headers
#include <stdio.h>
#include <memory.h>

// C++ system headers
// ...

// Headers from other projects
// ...

// Headers of current project
// ...

#define MAX_MAP_LINE (100)
#define MAX_MAP_COLUMN (100)
#define MAX_LEAVE_GRID_TIME (1000)
#define MAX_TIME (MAX_LEAVE_GRID_TIME * MAX_MAP_LINE * MAX_MAP_COLUMN + 1)

#define MAX_BEAST_COUNT (5)
#define MAX_BEAST_MEET_STATE (1 << MAX_BEAST_COUNT)
#define MAX_ONE_BEAST_ABILITY (1000)
#define MAX_TOTAL_BEAST_ABILITY (MAX_ONE_BEAST_ABILITY * MAX_BEAST_COUNT + 1)

typedef struct
{
    int leave_time;
    int beast_meet_state; // bit: 00000~11111 for 5 beasts
}GRID;

typedef struct
{
    int line;
    int column;
    unsigned int beast_meet_state; // bit: 00000~11111 for 5 beasts
}EXPAND_GRID;

typedef struct
{
    EXPAND_GRID grid_list[MAX_MAP_LINE * MAX_MAP_COLUMN];
    int grid_count;
}EXPAND_GRID_LIST;

GRID g_map[MAX_MAP_LINE][MAX_MAP_COLUMN];

// g_answer[i][j][k]:
// The time which had been cost when you entered the grid (i, j) [without leave time of this grid]
// with the beast state k [including the beast in (i, j)].
int g_answer[MAX_MAP_LINE][MAX_MAP_COLUMN][MAX_BEAST_MEET_STATE]; 

int g_beast_ability_sum[MAX_BEAST_MEET_STATE];
int g_map_width;
int g_map_height;
int g_K = 0;

void InputMap();
void InputBeast();
void Search();

int main()
{
    int i = 0;
    int answer = 0;

    InputMap();
    InputBeast();
    Search();

    answer = MAX_TIME;
    for (i = 0; i < MAX_BEAST_MEET_STATE; i++)
    {
        if (g_answer[g_map_height - 1][g_map_width - 1][i] < answer)
        {
            answer = g_answer[g_map_height - 1][g_map_width - 1][i];
        }
    }
    if (answer < MAX_TIME)
    {
        printf("%d\n", answer);
    }
    else
    {
        printf("Oh~,poor boys and girls!\n");
    }

    return 0;
}

void InputMap()
{
    int i = 0;
    int j = 0;
    int k = 0;
    scanf("%d%d", &g_map_height, &g_map_width);
    for (i = 0; i < g_map_height; i++)
    {
        for (j = 0; j < g_map_width; j++)
        {
            scanf("%d", &g_map[i][j].leave_time);
            g_map[i][j].beast_meet_state = 0;

            for (int k = 0; k < MAX_BEAST_MEET_STATE; k++)
            {
                g_answer[i][j][k] = MAX_TIME;
            }
        }
    }
    return;
}

void InputBeast()
{
    int i = 0;
    int j = 0;
    int line = 0;
    int column = 0;
    int beast_number = 0;
    int beast_ability[MAX_BEAST_COUNT];

    scanf("%d%d", &beast_number, &g_K);
    for (i = 0; i < beast_number; i++)
    {
        scanf("%d%d", &line, &column);
        g_map[line - 1][column - 1].beast_meet_state = (1 << i);
        scanf("%d", &beast_ability[i]);
    }

    for (i = 0; i < MAX_BEAST_MEET_STATE; i++)
    {
        g_beast_ability_sum[i] = 0;
        for (j = 0; j < beast_number; j++)
        {
            if (i & (1 << j) )
            {
                g_beast_ability_sum[i] += beast_ability[j];
            }
        }
    }
    return;
}

void AppendToGridList(EXPAND_GRID_LIST *grid_list, int new_grid_line, int new_grid_column, unsigned int new_beast_meet_state)
{
    grid_list->grid_list[grid_list->grid_count].line             = new_grid_line;
    grid_list->grid_list[grid_list->grid_count].column           = new_grid_column;
    grid_list->grid_list[grid_list->grid_count].beast_meet_state = new_beast_meet_state;
/*
    printf(
        "Expending: [%3d][%3d][%3d] = %6d\n",
        new_grid_line,
        new_grid_column,
        new_beast_meet_state,
        g_answer[new_grid_line][new_grid_column][new_beast_meet_state]
    );*/
    grid_list->grid_count++;
    return;
}

int IsDestination(int line, int column)
{
    if ( 
        (g_map_height == line) &&
        (g_map_width == column)
    )
    {
        return true;
    }
    return false;
}

int IsEnterable(int line, int column)
{
    if (line < 0)
    {
        return false;
    }

    if (line >= g_map_height)
    {
        return false;
    }

    if (column < 0)
    {
        return false;
    }

    if (column > g_map_width)
    {
        return false;
    }

    if (g_map[line][column].leave_time < 0)
    {
        return false;
    }

    return true;
}

int Expandable(int line, int column, int now_time, unsigned int now_beast_state)
{
    int          new_time = now_time + g_map[line][column].leave_time;
    unsigned int new_beast_state = 0;

    if (!IsEnterable(line, column) )
    {
        return false;
    }

    if (IsDestination(line, column) )
    {
        return true;
    }

    if (now_beast_state & g_map[line][column].beast_meet_state) // have met the beast in this grid
    {
        return false;
    }

    new_beast_state = (now_beast_state | g_map[line][column].beast_meet_state);

    if (
        (new_beast_state > 0) &&
        (g_map[line][column].leave_time > g_K - g_beast_ability_sum[new_beast_state] )
    )// too strong beasts
    {
        return false;
    }

    if (now_time >= g_answer[line][column][new_beast_state]) // TODO: some branch could be cut here: less time cost and less beast ability.
    {
        return false;
    }

    return true;
}

void CopyGridList(EXPAND_GRID_LIST *dest, EXPAND_GRID_LIST *src)
{
    dest->grid_count = src->grid_count;
    memcpy(dest->grid_list, src->grid_list, src->grid_count * sizeof(src->grid_list[0]) );
    return;
}

void Search()
{
    EXPAND_GRID_LIST now_list;
    EXPAND_GRID_LIST next_list;

    int i = 0;
    int j = 0;

    int          now_cost_time        = 0;
    unsigned int now_beast_meet_state = 0;

    int          new_grid_line        = 0;
    int          new_grid_column      = 0;
    int          new_cost_time        = 0;
    unsigned int new_beast_meet_state = 0;

    int direction_list[4][2] = {
        {-1,  0},
        { 1,  0},
        { 0, -1},
        { 0,  1}
    };

    now_list.grid_count = 0;
    next_list.grid_count = 0;

    for (i = 0; i < MAX_BEAST_MEET_STATE; i++)
    {
        g_answer[0][0][i] = 0;
    }
    AppendToGridList(&now_list, 0, 0, g_map[0][0].beast_meet_state);

    while (now_list.grid_count > 0)
    {
        next_list.grid_count = 0;
        for (int i = 0; i < now_list.grid_count; i++)
        {
            now_cost_time        = g_answer[now_list.grid_list[i].line][now_list.grid_list[i].column][now_list.grid_list[i].beast_meet_state];
            new_cost_time        = now_cost_time + g_map[now_list.grid_list[i].line][now_list.grid_list[i].column].leave_time;
            now_beast_meet_state = now_list.grid_list[i].beast_meet_state;
            for (j = 0; j < 4; j++)
            {
                new_grid_line        = now_list.grid_list[i].line   + direction_list[j][0];
                new_grid_column      = now_list.grid_list[i].column + direction_list[j][1];
                new_beast_meet_state = now_beast_meet_state | g_map[new_grid_line][new_grid_column].beast_meet_state;
                if (Expandable(new_grid_line, new_grid_column, now_cost_time, now_beast_meet_state) )
                {
                    g_answer[new_grid_line][new_grid_column][new_beast_meet_state] = new_cost_time;
                    AppendToGridList(&next_list, new_grid_line, new_grid_column, new_beast_meet_state);
                }
            }
        }

        CopyGridList(&now_list, &next_list);
    }

    return;
}

追问

你好，可以先告诉我bfs算法怎么解决野兽追踪的问题吗

你好，可以先告诉我bfs算法怎么解决野兽追踪的问题吗

追答

看注释

// g_answer[i][j][k]:
// The time which had been cost when you entered the grid (i, j) [without leave time of this grid]
// with the beast state k [including the beast in (i, j)].

g_answer[i][j][k]表示：走到坐标(i, j)，遇到的野兽状况为k时，所需的最小时间。

这里k按位保存野兽相遇状况（beast meet state），比如一共5只野兽，编号依次是0~4，那么：

二进制00000（十进制0）表示没有遇到野兽。

二进制00001（十进制1）表示遇到了0号野兽。

二进制10110（十进制22）表示遇到了1号、2号和4号野兽。

二进制11111（十进制31）表示遇到了所有野兽。

这种方法只有当野兽数量极少（不超过10）的时候才能用。

这样，对于每一个状态(i, j, k)，我们知道当前的坐标及遇到过哪些野兽，于是就能推测出下一步是否能走了。

我用了数组g_beast_ability_sum保存了每一种野兽相遇状态（00000~11111）下野兽追踪能力总和，以避免重复计算。

追问

很抱歉,你的代码是wrong answer
不过没关系,我想知道你是怎么解决回溯问题的,如果说使用bfs算法,那不应有回溯,因为每个位置只判断一次,但由于野兽的存在,某些位置要判断多次
比如一个位置如果按最快方案走可能会被野兽缠上,导致到后面某一步over,或者一开始不按最快而是避过野兽走的话却不会遇到这种情况,代码没关系,我想知道这个你是怎么就解决的

追答

其实我想要题目链接就是担心我的算法有点问题……
我完全没有回溯，而是类似模拟退火的方法，逐渐逼近结果。
换言之，并非每个位置只判断一次，而是如果两次到达同一个位置，第二次走的格子多但总耗时短，那么程序会重新扩展那个位置，而不是因为”走过了“而不走。
具体代码在函数Expandable里最后一次return false的那个if分支。如果当前时间比已有答案少的话，还是return true（可扩展）的。

追问

如果对某个节点进行两次或以上的运算那可能会运行过久，time limit可是只有1000ms，而且我还发现一个问题，bfs并不恰当，因为每天路是有权值的，并不是走的步数越少就越近的

追答

我考虑过如果还是TLE就得改成Dijkstra算法，不过那算法联合三维数组比较麻烦，所以我先用了普通BFS。由于数据规模才10000格子，1秒是一般是足够的。
另外，正是因为不是走的步数越少就越近，所以才需要多次扩展。步数相同时的重复扩展其实能用排序处理。步数不同时的扩展，正如我上次追答：
如果两次到达同一个位置，第二次走的格子多（！）但总耗时短（！），那么程序会重新扩展那个位置

追问

好,我实现一下代码,我还有其他两个问题,你能先帮我看看吗,也有很多分哦
http://zhidao.baidu.com/question/1509659764186674980.html?quesup2&oldq=1
http://zhidao.baidu.com/question/1817618498901290668.html?quesup2&oldq=1

Answer 2

果然很难，题意都不懂