没觉得多难……三维数组的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