三维空间的dfs和bfs
去枚举每一步的6个方向的时候都会用到三个偏移量数组
dx[]={1,0,0,-1,0,0};
dy[]={0,1,0,0,-1,0};
dz[]={0,0,1,0,0,-1};
// 这样一个for就可以枚举出六个方向
for(int i = 0; i < 6; i ++)
{
int a = x + dx[i];
int b = y + dy[i];
int c = z + dz[i];
}
acwing 4708. 立方体 (三维空间dfs)
原题链接:https://www.acwing.com/problem/content/4711/
思路
范围小于30,可以使用dfs暴搜
写一个dfs求得从该点开始搜到几个之前没搜过的格子
搜过的格子打个标记就行,将其改成#
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15;
int n,m,k;
char g[N][N][N];
// 偏移量数组,上每一个维度(x,y,z)都是+1或-1
int dx[] = {1,0,0,-1,0,0};
int dy[] = {0,1,0,0,-1,0};
int dz[] = {0,0,1,0,0,-1};
int dfs(int x,int y,int z)
{
g[x][y][z] = '#';
int res = 1;
for(int i = 0; i < 6;i ++)
{
int a = dx[i] + x,b = dy[i] + y,c = dz[i] + z;
if(a < 0 || a >= k || b < 0 || b >= n || c < 0 || c >= m || g[a][b][c] == '#')continue;
res += dfs(a,b,c);
}
return res;
}
int main()
{
cin >> k >> n >> m;
for(int u = 0;u < k; u ++)
for(int i = 0;i < n; i ++)
cin >> g[u][i];
int x = 0;
int y,z;
cin >> y >> z;
int ans = dfs(0,y-1,z-1);
cout << ans;
return 0;
}
acwing 1096. 地牢大师(三维空间bfs)
原题链接:https://www.acwing.com/problem/content/1098/
思路:
像平常的bfs求最短路一样,开一个dist[][][],并初始化成-1
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 110;
struct Point
{
int x,y,z;
};
char g[N][N][N];
int L,R,C;
int dist[N][N][N];
int dx[] = {1,0,0,-1,0,0};
int dy[] = {0,1,0,0,-1,0};
int dz[] = {0,0,1,0,0,-1};
int bfs(Point start,Point end)
{
queue<Point> q;
memset(dist, -1, sizeof dist);
int x0 = start.x, y0 = start.y, z0 = start.z;
dist[x0][y0][z0] = 0;
q.push(start);
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = 0; i < 6;i ++)
{
int x = t.x+dx[i], y = t.y+dy[i], z = t.z+dz[i];
if(x < 0 || x >= L || y < 0 || y >= R || z < 0 || z >= C) continue;
if(g[x][y][z] == '#' || dist[x][y][z] != -1) continue;
dist[x][y][z] = dist[t.x][t.y][t.z] + 1;
q.push({x,y,z});
}
}
return dist[end.x][end.y][end.z];
}
int main()
{
while (scanf("%d%d%d", &L, &R, &C), L || R || C)
{
Point start, end;
for (int i = 0; i < L; i ++ )
for (int j = 0; j < R; j ++ )
{
scanf("%s",g[i][j]); // 这样写不用处理读入回车的问题
for (int k = 0; k < C; k ++ )
{
// scanf("%c",&g[i][j][k]); // 这样写会读入'\n'符
char c = g[i][j][k];
if (c == 'S') start = {i, j, k};
else if (c == 'E') end = {i, j, k};
}
}
int distance = bfs(start, end);
if (distance == -1) puts("Trapped!");
else printf("Escaped in %d minute(s).\n", distance);
}
return 0;
}
标签:dist,start,int,dfs,bfs,++,三维空间
From: https://www.cnblogs.com/rdisheng/p/16820173.html