首页 > ACM题库 > HDU-杭电 > HDU 3502-Huson’s Adventure Island-BFS-[解题报告]HOJ
2014
04-09

HDU 3502-Huson’s Adventure Island-BFS-[解题报告]HOJ

Huson’s Adventure Island

问题描述 :

A few days ago, Tom was tired of all the PC-games, so he went back to some old FC-games. "Hudson’s Adventure Island" was his favorite which he had played thousands of times. But to his disappointed, the more he played, the more he lost. Tom soon gave up the game.

Calculation 2

Now, he invents an easier game on the base of “Hudson’s Adventure Island”. He wants to know whether the new game is easy enough. So he came to you for help.
To simplify the problem, you can assume there is matrix-map contains m(0 < m < 256) rows, n(0 < n < 256) columns, an entrance on the top-left corner (0, 0), an exit on the bottom-right corner (m-1, n-1). Each entry of the matrix contains a integer k.The range of k is defined below:
a)k = 0,it is a free space one can go through.
b)k = -1,it is an obstacle one can’t go through.
c)0 < k < 10000,it is a fruit one can go through and gain k points of energy.
d)k >= 0 at the entrance point and the end point.
At the begin, the hero has 0 points of energy and he can go four directions (up, down, left, right). Each move he makes cost 1 point of energy. No energy no move. If he can’t make a move or get to the exit, he loses the game. The number of fruit is 17 at most.

输入:

The input consists of multiple test cases. Each test case starts with two positive integers m, n. Then follows m lines, each line contain n integers.

输出:

The input consists of multiple test cases. Each test case starts with two positive integers m, n. Then follows m lines, each line contain n integers.

样例输入:

4 4
8 0 0 0
-1 -1 -1 0
-1 -1 -1 0
0 6 0 0
3 3
4 0 0
0 0 0
0 0 0
4 4
5 0 0 0
0 -1 -1 0
0 -1 -1 0
0 0 0 0

样例输出:

4
0
you loss!


Hint
The hero can pass the exit. When he gets the exit point, he can choose to get out to finish the game or move on to gain more points of energy.

这题先用BFS初始化各水果间的距离,以及它们到终点的距离,然后状态DP。

不过有个小小的陷阱,终点上如果有水果,可能要走两次。

贡献一组数据:

4 4

8 0 0 0

-1 -1 -1 0

-1 -1 -1 0

10 0 0 2

答案是:

8

#include <iostream>
#include <queue>
using namespace std;
const int inf = 1000000000;
struct Node
{
int x, y;
};
int map[256][256], cost[256][256];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int n, m;
Node fruit[18];
int val[17], cunt;
int dis[18][18];
queue<Node> Q;
int best[1<<17][17];
bool Bound(int x, int y)
{
return x >= 0 && x < n && y >= 0 && y < m;
}
void BFS(Node start)
{
int i, j;
Node now, nex;
for (i = 0; i < n; i++)
{
for (j = 0; j < m; j++)
{
cost[i][j] = inf;
}
}
cost[start.x][start.y] = 0;
Q.push(start);
while (!Q.empty())
{
now = Q.front();
Q.pop();
for (i = 0; i < 4; i++)
{
nex.x = now.x + dir[i][0];
nex.y = now.y + dir[i][1];
if (Bound(nex.x, nex.y) && map[nex.x][nex.y] != -1 && cost[nex.x][nex.y] == inf)
{
cost[nex.x][nex.y] = cost[now.x][now.y] + 1;
Q.push(nex);
}
}
}
}
void DP()
{
int i, j, v;
Node now, nex;
for (i = 1; i < (1 << cunt); i++)
{
for (j = 0; j < cunt; j++)
{
best[i][j] = -1;
}
}
best[1][0] = val[0];
now.x = 1; now.y = 0;
Q.push(now);
while (!Q.empty())
{
now = Q.front();
Q.pop();
for (i = 1; i < cunt; i++)
{
if ((now.x & (1 << i)) == 0)
{
nex.x = (now.x | (1 << i));
nex.y = i;
v = best[now.x][now.y] - dis[now.y][nex.y];
if (v < 0)
{
continue;
}
v = v + val[nex.y];
if (v > best[nex.x][nex.y])
{
best[nex.x][nex.y] = v;
Q.push(nex);
}
}
}
}
}
int main()
{
int i, j, ans;
while (scanf("%d %d", &n, &m) != EOF)
{
cunt = 0;
for (i = 0; i < n; i++)
{
for (j = 0; j < m; j++)
{
scanf("%d", &map[i][j]);
if (map[i][j] > 0)
{
fruit[cunt].x = i;
fruit[cunt].y = j;
val[cunt++] = map[i][j];
}
}
}
if (n == 1 && m == 1)
{
printf("%d/n", map[0][0]);
continue;
}
if (map[0][0] == 0)
{
printf("you loss!/n");
continue;
}
// 把终点也加入进去计算距离
fruit[cunt].x = n - 1;
fruit[cunt].y = m - 1;
for (i = 0; i <= cunt; i++)
{
BFS(fruit[i]);
for (j = 0; j <= cunt; j++)
{
dis[i][j] = cost[fruit[j].x][fruit[j].y];
}
}
DP();
ans = -1;
for (i = 1; i < (1 << cunt); i++)
{
for (j = 0; j < cunt; j++)
{
if (ans < best[i][j] - dis[j][cunt])
{
ans = best[i][j] - dis[j][cunt];
}
}
}
if (ans >= 0)
{
printf("%d/n", ans);
}
else
{
printf("you loss!/n");
}
}
return 0;

参考:http://blog.csdn.net/racebug2010/article/details/6177834


  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。