Saturday, 14 January 2017

BFS in a 3D grid

#include<bits/stdc++.h>
using namespace std;
int graph[35][35][35];
int visited[35][35][35];
int level[35][35][35];
int x[6]={1,-1,0,0,0,0};
int y[6]={0,0,1,-1,0,0};
int z[6]={0,0,0,0,1,-1};
int main()
{
    int r,c,w;
    cin>>w>>r>>c;//w:how many levels,c:row in each level,c:column in each level
    memset(graph,0,sizeof(graph));
    for(int i=0;i<w;i++)
    {
        for(int j=0;j<r;j++)
        {
            for(int k=0;k<c;k++)
            {
                cin>>graph[i][j][k];//use 1 and 0 as input
            }
        }
    }
    memset(visited,0,sizeof(visited));
    memset(level,0,sizeof(level));
    queue<int>q;
    int stx,sty,stz,enx,eny,enz;
    cin>>stx>>sty>>stz;
    cin>>enx>>eny>>enz;
    visited[stx][sty][stz]=true;
    level[stx][sty][stz]=0;
    q.push(stx);
    q.push(sty);
    q.push(stz);
    int ans;
    bool flag=0;
    while(!q.empty())
    {
        int f1,f2,f3;
        f1=q.front();
        q.pop();
        f2=q.front();
        q.pop();
        f3=q.front();
        q.pop();
        for(int in=0;in<6;in++)
        {
            int v1,v2,v3;
            v1=f1+x[in];
            v2=f2+y[in];
            v3=f3+z[in];
            if(!visited[v1][v2][v3]&&!level[v1][v2][v3]&&graph[v1][v2][v3]==1&&(v1>=0&&v1<w&&v2>=0&&v2<r&&v3>=0&&v3<c))
            {
                {
                    level[v1][v2][v3]=level[f1][f2][f3]+1;
                    //cout<<"LEVEL:"<<level[v1][v2]<<endl;
                    if(v1==enx&&v2==eny&&v3==enz)
                    {
                        flag=1;
                        ans=level[v1][v2][v3];
                    }
                    q.push(v1);
                    q.push(v2);
                    q.push(v3);
                    visited[v1][v2][v3]=true;
                }
            }
        }
    }
    if(flag)
        cout<<ans<<endl;
    else
        cout<<-1<<endl;
    return 0;
}

No comments:

Post a Comment