首页 > 其他分享 >Acwing 4708 . 立方体(三维bfs)

Acwing 4708 . 立方体(三维bfs)

时间:2022-10-27 20:45:27浏览次数:94  
标签:dist LL 三维 4708 bfs que && Acwing

https://www.acwing.com/problem/content/4711/

题目没什么难度,但是就是三维有些东西不经常定义记不住。写个题解记录一下吧
Acwing 1096.地牢大师
https://www.acwing.com/problem/content/1098/
同为三维bfs

三维方向定义(6个方位)

LL dx[]={-1,0,0,0,0,1};
LL dy[]={0,0,0,1,-1,0};
LL dz[]={0,1,-1,0,0,0}; 

三维长宽高存储

struct Point
{
    LL x;
    LL y;
    LL z;
};//(一定要记得这个分号!不然会报错)

queue存储调用

queue<Point> que;

完整代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL N=200200,M=100;
LL k,n,m,l,r;
LL dist[M][M][M];
char a[M][M][M];
LL dx[]={-1,0,0,0,0,1};
LL dy[]={0,0,0,1,-1,0};
LL dz[]={0,1,-1,0,0,0}; 
struct Point
{
    LL x;
    LL y;
    LL z;
};
LL bfs(LL o,LL p,LL q)
{
    memset(dist,-1,sizeof dist);
    dist[o][p][q]=0;
    queue<Point> que;
    que.push({o,p,q});
    while(que.size())
    {
        auto t=que.front();
        que.pop();
        for(LL i=0;i<6;i++)
        {
            LL xx=dx[i]+t.x,yy=dy[i]+t.y,zz=dz[i]+t.z;
            if(xx>=1&&xx<=k&&yy>=1&&yy<=n&&zz>=1&&zz<=m&&dist[xx][yy][zz]==-1&&a[xx][yy][zz]!='#')
            {
                dist[xx][yy][zz]=dist[t.x][t.y][t.z]+1;
                que.push({xx,yy,zz});
            }
        }
    }
    return dist[k][n][m];
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--)
    {
        cin>>k>>n>>m;//k层,每一层都是n*m
        for(int i=1;i<=k;i++)
        {
            for(int j=1;j<=n;j++)
            {
                for(int q=1;q<=m;q++)
                {
                    cin>>a[i][j][q];
                }
            }
        }
        cin>>l>>r;
        bfs(1,l,r);
        LL ans=0;
        for(int i=1;i<=k;i++)
        {
            for(int j=1;j<=n;j++)
            {
                for(int q=1;q<=m;q++)
                {
                    if(dist[i][j][q]>=0) ans++;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

标签:dist,LL,三维,4708,bfs,que,&&,Acwing
From: https://www.cnblogs.com/Vivian-0918/p/16833677.html

相关文章

  • ACWing 3549 -- dp&&滚动数组
    题目描述最长非递减子序列思路Reference代码......
  • ACWing 3548 -- 离线算法
    题目描述双端队列思路参考代码......
  • spfa和bfs的区别
    \(spfa\)和\(bfs\)的区别\(spfa\)在形式上和\(bfs\)非常类似,不同的是\(bfs\)中一个点出了队列就不可能重新进入队列,但是\(spfa\)中一个点可能在出队列之后再次被放入队列,......
  • Acwing 788.逆序对的数量
    #include<bits/stdc++.h>usingnamespacestd;constintN=1e+5;inta[N],tmp[N];typedeflonglongll;#注意题目条件llmerge_sort(intq[],intl,intr){......
  • Acwing 787.归并排序
    注意理解代码层次。#include<bits/stdc++.h>usingnamespacestd;#defineN10e5+10;//数组开太小容易栈溢出inta[N],tmp[N];voidmerge_sort(intq[],intl......
  • AcWing 1022. 宠物小精灵之收服
    宠物小精灵之收服(二维费用背包问题)原题链接:https://www.acwing.com/problem/content/1024/思路先做一个阅读理解每一个小精灵只能收一次->01背包接下来去考虑体积、......
  • Acwing 快速排序
    基于分治的思想,每次划分后,保证基准(x)前的数都比基准小,其后的树都比基准大即可。#include<iostream>usingnamespacestd;constintN=100010;intq[N];voidquic......
  • BFS最短路径(求x到y的最少计算次数)
     给定两个-100到100的整数x和y,对x只能进行加1,减1,乘2操作,问最少对x进行几次操作能得到y?例如:a=3,b=11:可以通过3*2*2-1,3次操作得到11;a=5,b=8:可以通过(5-1)*2,2次操作得到......
  • BFS--宽搜求最短路径
    1010#S######.#......#..#.#.##.##.#.#........##.##.####....#....#.#######.#....#......####.###.....#...G##是障碍,.是通道,S是起点,G是终点求出最短路径长度......
  • ACWing 4480 -- 二分&&双指针&&思维
    题目描述倒垃圾思路其实就是思维题,题意很简单,找到一个居民左侧和右侧(如果存在的话)的垃圾桶中最近的那个垃圾桶,然后让那个垃圾桶的计数器加一。从题目中挖掘的性质:左......