【练习】Jelly
Jelly
https://ac.nowcoder.com/acm/problem/201613
题目
题目描述：Nancy喜欢吃果冻！
Nancy钻进了一个n×n×n的果冻里，她想从(1,1,1)一路上、下、左、右、前、后六个方向吃到(n,n,n)。
但果冻毕竟是有许多口味的，标记为*的口味是Nancy不愿意吃的，其余的果冻均标记为.。
Nancy不想吃坏肚子，于是她想尽可能少的吃果冻。
下面给出果冻的情况，请你帮忙计算一下她能吃多少块果冻叭！
输入描述：
第一行：一个整数n。接下来n层，每组n行，每行n列，表示果冻(i,j,k)的情况（如题目描述所述）。
数据满足：1≤n≤100，保证果冻(1,1,1)不是Nancy不愿意吃的。
输出描述：
如果可以到达(n,n,n)，请输出路上吃的果冻数量，否则请输出-1。
解析
题就是简单的bfs
操作操作：
- 三维数组作为地图（mp数组）保存题目信息，建立一个已访问数组（visited数组）保存节点的访问信息，保证每个节点不被重复访问。
- 用队列对地图进行遍历。先将起点进队，然后访问起点可以到达的所有节点（地图外和禁止区域当然就不让访问了）
- 然后依次类推，每次将队首节点拿出来访问，直到访问到终点。
- 因为我们队列保存的是结构体，每个节点自带步数。（步数自然等于访问他的节点+1）所以输出该节点的步数就好了。
代码
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int MAX = 1e2 + 7;
//代码预处理
int walk[6][3] = { {1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1} };//三轴移动
int visited[MAX][MAX][MAX], mp[MAX][MAX][MAX], n;//已访问数组，地图，大小
typedef struct {
int x, y, z, eat;//坐标与吃的数量
} Node;
int judge(Node next);//判断接下来访问的节点是否是合法位置（墙或者不能走的格子）
int dfs();//广度优先遍历
int main() {
js;
cin >> n;
memset(mp, -1, sizeof(mp));
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
char ch; cin >> ch;
if (ch == '.') mp[i][j][k] = 0;
}
//初始化地图数组
cout << dfs() << endl;
return 0;
}
int judge(Node next) {
if (mp[next.x][next.y][next.z]) return 0;//判墙或者不能走的节点
if (visited[next.x][next.y][next.z]) return 0;//判是否走过
return 1;
}
int dfs() {
memset(visited, 0, sizeof(visited));
visited[1][1][1] = 1;
Node top; top.x = 1; top.y = 1; top.z = 1; top.eat = 1;
queue<Node> que; que.push(top);
//队列与访问数组初始化
while (!que.empty()) {
top = que.front(); que.pop();
if (top.x == n && top.y == n && top.z == n) return top.eat;
//抵达终点则有数量返回，否则最后会全部出队返回-1
for (int i = 0; i < 6; i++) {
Node next;
next.x = top.x + walk[i][0];
next.y = top.y + walk[i][1];
next.z = top.z + walk[i][2];
next.eat = top.eat + 1;
//得到下一个节点
if (judge(next)) {
que.push(next);
visited[next.x][next.y][next.z] = 1;
}
//可走则进队
}
}
return -1;
} 牛客算法竞赛入门课题解 文章被收录于专栏
憨憨的专栏
