首页 > 其他分享 >三维空间的dfs和bfs

三维空间的dfs和bfs

时间:2022-10-24 07:55:17浏览次数:78  
标签:dist start int dfs bfs ++ 三维空间

三维空间的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

相关文章

  • 初学bfs
    dfs利用的是栈,bfs利用的是队列如同y总所说的,不需要理解如何用队列实现一个bfs而是跟着y总,告诉我们怎么做,然后我们自己判断一下这种是不是bfs如图:取出的顺序和加入的......
  • 深度优先搜索求最短路径DFS C#实现
    搜索效果 C#项目文件可以点击下载   搜索最短路径的代码:///<summary>///DFS求最短路径///</summary>///<paramname="cX">当前点X坐标</param>///<par......
  • bfs + bitmask
    864. ShortestPathtoGetAllKeysYouaregivenan mxn grid grid where:'.' isanemptycell.'#' isawall.'@' isthestartingpoint.Lowercas......
  • 八数码难题——BFS
    原题链接:https://www.acwing.com/problem/content/847/通常情况下很难看出这是一道BFS题或者说看不出怎么表示状态,毕竟它的状态涉及到整个矩阵但是可以用一种unordered_......
  • .net core-利用PdfSharpCore和SkiaSharp.QrCode 添加PDF二维码页眉
    前序   由于去年的一个项目需要在PDF添加公司二维码,当时在网上找了很多操作PDF方案,第一种Aspose.PDF,很遗憾 Aspose.PDF有添加版权的背景还是页脚我忘记了,不适合......
  • Leetcode 2440 -- dfs&&枚举
    题目描述创建价值相同的连通块思路代码拓展:统计子树的大小当图是一棵树(无环)的时候,如果树有向,什么都不用设置,否则,额外传入一个fa如果有环,设置一个st数组。......
  • hdfs hadoop
      $HADOOP_HOMEecho $HADOOP_HOME 配置文件在这个目录:$HADOOP_HOME/etc/hadoop 1、文件coer-site.xml  2、文件hdfs-site.xml(重点核心文件)   ......
  • HDFS相关问题处理
    机房搬迁后datanode启动失败,报错如下:2022-10-2110:28:40,551INFOorg.apache.hadoop.hdfs.server.common.Storage:Lockon/HDATA/1/dfs/local/in_use.lockacquired......
  • Snowy Mountain (找规律来贪心+ 多源特殊bfs+根号n)
    题目大意:给定一棵 nn 个点的树,其中每个点可能是黑色或白色。一个点的高度定义为其距离最近黑色节点的距离。你初始在 ii 号节点上,势能为 00,可以做以下两种操作:......
  • Linux安装pdfsizeopt来压缩PDF
    $mkdir~/pdfsizeopt$cd~/pdfsizeopt$wget-Opdfsizeopt_libexec_linux.tar.gzhttps://github.com/pts/pdfsizeopt/releases/download/2017-01-24/pdfsizeopt_lib......