FZU1491 机器人测试
Problem Description 题目链接
为了测试我们的足球机器人的性能，我们设计如下的测试方法：
将一个机器人放在一个n*n的矩形阵列的某个格子中，它每次可以向与它所处的格子相邻的4个格子中的任何一个移动。
在这个阵列的一些格子中，摆放着能量，机器人希望能够得到这些能量。但是，这个阵列中存在着两种障碍物，一种障碍物使得机器人无法向前移动进入这个格子；第二种障碍物机器人虽然可以通过，但是，通过这样一个障碍物的时候，它先前所吃到的所有的能量都将消失。你的任务是，对于给定的一个阵列以及它的描述，计算出这个机器人所能够获得的最大能量值。
Input
本题有多组输入数据，你必须处理到EOF为止
输入数据的第一行表示输入矩阵的维数n，接下来n行，每行有n个元素，给出一个n*n的矩阵(n<=1000)。这个矩阵中，0表示这个格子上什么都没有，-1是机器人开始的位置，-2表示的是第一种障碍物，-3表示的是第2种障碍物。其他非负整数值表示的是能量的数值。
Output
输出仅一行，表示机器人所能获得的最大能量。
我们保证最后结果在[0, 230]的范围内。
Sample Input
4 10000 -2 0 0 -2 1 -1 0 -3 -3 0 0 1000 -3 0 0
Sample Output
1000
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
/*
思路 第一步：因为-3会清空能量，一开始可以将-3和-2看成围墙，看看图中可以分割几块小图，类似LeetCode200计算岛屿数量,并给岛屿编号
第二步：从机器人出发 再一次BFS求所能经过的最大值，-3看成通路
*/
int N, map[1005][1005], visit[1005][1005], val[1000005], num, res;
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
//边界和访问检查
bool check(int x, int y)
{
if (x < 1 || y < 1 || x > N || y > N || visit[x][y])
return false;
return true;
}
struct Pos
{
int x, y;
};
//第一次计算岛屿
void Bfs(int x, int y)
{
Pos p;
p.x = x;
p.y = y;
visit[x][y] = 1;
if (map[x][y] > 0)
val[num] = map[x][y];
else
{
val[num] = 0;
}
map[x][y] = num;
queue<Pos> q;
q.push(p);
while (!q.empty())
{
p = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int _x = p.x + dir[i][0], _y = p.y + dir[i][1];
if (check(_x, _y))
{
visit[_x][_y] = 1;
//非墙
if (map[_x][_y] >= -1)
{
if (map[_x][_y] > 0)
val[num] += map[_x][_y];
map[_x][_y] = num;
Pos t;
t.x = _x;
t.y = _y;
q.push(t);
}
}
}
}
}
//第二次寻找最大值
void BfsSearchMax(int x, int y)
{
Pos p;
p.x = x;
p.y = y;
visit[x][y] = 1;
res = 0;
queue<Pos> q;
q.push(p);
while (!q.empty())
{
p = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int _x = p.x + dir[i][0], _y = p.y + dir[i][1];
if (check(_x, _y))
{
visit[_x][_y] = 1;
//非墙
if (map[_x][_y] != -2)
{
if (map[_x][_y] > 0 && res < val[map[_x][_y]])
res = val[map[_x][_y]];
Pos t;
t.x = _x;
t.y = _y;
q.push(t);
}
}
}
}
}
int main()
{
while (scanf("%d", &N) != EOF)
{
int sx = 0, sy = 0;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
{
scanf("%d", &map[i][j]);
visit[i][j] = 0;
if (map[i][j] == -1)
{
sx = i;
sy = j;
}
}
//num 地图编号 同一块小图编号相同
num = 1;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
//说明未访问
if (visit[i][j] == 0 && map[i][j] >= -1)
{
Bfs(i, j);
num++;
}
}
}
memset(visit, 0, sizeof(visit));
BfsSearchMax(sx, sy);
printf("%d\n", res);
}
}
PS:BFS能A题，但是我用DFS出现RuntimError不知道有没有大佬看看哪里出错了
#include <stdio.h>
#include <string.h>
int N, map[1005][1005], visit[1005][1005], val[1000001], num, res;
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
//边界和访问检查
bool check(int x, int y)
{
if (x < 1 || y < 1 || x > N || y > N || visit[x][y])
return false;
return true;
}
//计算池塘的Val 此时-2 -3当作墙
void dfs(int x, int y)
{
for (int i = 0; i < 4; i++)
{
int _x = x + dir[i][0], _y = y + dir[i][1];
if (check(_x, _y))
{
visit[_x][_y] = 1;
if (map[_x][_y] >= -1) //说明可以访问
{
if (map[_x][_y] > 0)
val[num] += map[_x][_y];
map[_x][_y] = num;
dfs(_x, _y);
}
}
}
}
//计算最大值 此时-3能通过
void dfsMax(int x, int y)
{
for (int i = 0; i < 4; i++)
{
int _x = x + dir[i][0], _y = y + dir[i][1];
if (check(_x, _y))
{
visit[_x][_y] = 1;
//说明可以通过
if (map[_x][_y] != -2)
{
if (map[_x][_y] > 0 && res < val[map[_x][_y]])
res = val[map[_x][_y]];
dfsMax(_x, _y);
}
}
}
}
int main()
{
while (scanf("%d", &N) != EOF)
{
int sx=0, sy=0;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
{
scanf("%d", &map[i][j]);
visit[i][j] = 0;
if (map[i][j] == -1)
{
sx = i;
sy = j;
}
}
//初始化NUM
num = 1;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
//说明未访问
if (visit[i][j] == 0 && map[i][j] >= -1)
{
if (map[i][j] > 0)
val[num] = map[i][j];
else
{
val[num] = 0;
}
map[i][j] = num;
visit[i][j] = 1;
dfs(i, j);
num++;
}
}
}
memset(visit, 0, sizeof(visit));
res = 0;
visit[sx][sy] = 1;
dfsMax(sx, sy);
printf("%d\n", res);
}
}