HDOJ-2102-A计划 解题报告
发布时间
阅读量：
阅读量
此乃一道关于三维图的搜索问题。仅限于中文表述，并无需进一步解释题意。本问题关注的是勇士能否在限定时间内将公主带走。因此采用广度优先搜索策略最为适宜。此外需要注意的是，在这个问题中存在三个维度变量，并且第三维仅包含两种可能取值的情况。这意味着每个节点可探索的相邻节点数量相对有限。
注意：1.遇到‘#’时空穿梭机必定会传送，没有其他选择；
2.根据1可知，当两边都是‘#’或者一边是‘#’另一边是‘*’时、、、（我只想说勇士死定了）；
3.起点和终点可以是同一层；
4.两张地图之间有空行，不熟悉字符串输入的人可要小心了；
5.传送不消耗时间
下面是我的解题代码：BFS解题
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define N 12
using namespace std;
struct point //定义节点结构体
{
int z, x, y; //三维坐标，z设置为第一维
int step; //到达当前节点的步数
};
char map[2][N][N];
int vis[2][N][N]; //初始化为-1代表该点没有走过，否则为到达该点的最短时间
int t, n, m, costtime;
queue <point> q; //使用队列
point start, end; //初始位置和公主位置
void Read(); //输入
void Init(); //初始化
void DataProcess(); //数据处理
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d %d %d", &n, &m, &costtime);
Read();
Init();
DataProcess();
}
return 0;
}
void Read()
{
int i;
for (i=0; i<n; ++i)
{
scanf("%s", map[0][i]);
}
for (i=0; i<n; ++i)
{
scanf("%s", map[1][i]);
}
return;
}
void Init()
{
int i, j;
for (i=0; i<n; ++i)
{
for (j=0; j<m; ++j)
{
vis[0][i][j] = vis[1][i][j] = -1;
if (map[0][i][j] == 'S')
{
start.x = i;
start.y = j;
start.z = 0;
}
if (map[1][i][j] == 'S')
{
start.x = i;
start.y = j;
start.z = 1;
}
if (map[0][i][j] == 'P')
{
end.x = i;
end.y = j;
end.z = 0;
}
if (map[1][i][j] == 'P')
{
end.x = i;
end.y = j;
end.z = 1;
}
}
}
vis[start.z][start.x][start.y] = start.step = 0; //步数即为时间，初始节点为0
q.push(start); //初始节点加入队列
return;
}
void DataProcess()
{
point a, b;
while (!q.empty()) //全部节点搜索完毕则退出
{
a = q.front();
q.pop();
if (map[a.z][a.x][a.y] == '#') //特殊情况
{
b.x = a.x;
b.y = a.y;
b.z = a.z == 0 ? 1 : 0;
//发现死路则取消搜索邻节点
if (map[b.z][b.x][b.y] == '*' || map[b.z][b.x][b.y] == '#' || vis[b.z][b.x][b.y] != -1) continue;
vis[b.z][b.x][b.y] = b.step = a.step;
q.push(b);
continue; //到达时空穿梭机只能传送没有其他选择
}
//以下是搜索上下左右四个方向的邻节点
if (a.x + 1 < n && map[a.z][a.x+1][a.y] != '*' && vis[a.z][a.x+1][a.y] == -1)
{
b.x = a.x + 1;
b.y = a.y;
b.z = a.z;
vis[b.z][b.x][b.y] = b.step = a.step + 1;
q.push(b);
}
if (a.x - 1 >= 0 && map[a.z][a.x-1][a.y] != '*' && vis[a.z][a.x-1][a.y] == -1)
{
b.x = a.x - 1;
b.y = a.y;
b.z = a.z;
vis[b.z][b.x][b.y] = b.step = a.step + 1;
q.push(b);
}
if (a.y + 1 < m && map[a.z][a.x][a.y+1] != '*' && vis[a.z][a.x][a.y+1] == -1)
{
b.x = a.x;
b.y = a.y + 1;
b.z = a.z;
vis[b.z][b.x][b.y] = b.step = a.step + 1;
q.push(b);
}
if (a.y - 1 >= 0 && map[a.z][a.x][a.y-1] != '*' && vis[a.z][a.x][a.y-1] == -1)
{
b.x = a.x;
b.y = a.y - 1;
b.z = a.z;
vis[b.z][b.x][b.y] = b.step = a.step + 1;
q.push(b);
}
}
if (vis[end.z][end.x][end.y] <= costtime && vis[end.z][end.x][end.y] != -1)
{
puts("YES");
}
else
{
puts("NO");
}
return;
}全部评论 (0)
还没有任何评论哟~