## BFS

Let's talk about algorithms!

Moderator: Board moderators

slxst
New poster
Posts: 23
Joined: Mon Oct 16, 2006 2:18 am

### BFS

I was trying to solve problem 532 Dungeon Master

This code got TLE (in 3 sec. it didn't solve the problem):

Code: Select all

``````struct Node {
int x;
int y;
int z;
int distance;
Node(int x = -1, int y = -1, int z = -1, int d = 0) : x(x), y(y), z(z), distance(d) {};
};

int bfs(const vector< vector<string> >& map, const int L, const int H, const int W, const Node& beginning) {
queue<Node> toProcess;
toProcess.push(beginning);

vector< vector< vector<bool> > > processed(L, vector< vector<bool> >(H, vector<bool>(W, false)));
processed[beginning.x][beginning.y][beginning.z] = true;

while(!toProcess.empty()) {
Node actual = toProcess.front(); toProcess.pop();
if(map[actual.x][actual.y][actual.z] == 'E') {
return actual.distance;
}
static const int dx[] = { 0, 0, 0, 0,-1, 1};
static const int dy[] = { 0, 0,-1, 1, 0, 0};
static const int dz[] = {-1, 1, 0, 0, 0, 0};
for(int i = 0; i < 6; ++i) {
int nx = actual.x + dx[i];
int ny = actual.y + dy[i];
int nz = actual.z + dz[i];
if(nx >= 0 && nx < L && ny >= 0 && ny < H && nz >=0 && nz < W && !processed[nx][ny][nz] && map[nx][ny][nz] != '#') {
Node neighbor(nx, ny, nz, actual.distance + 1);
toProcess.push(neighbor);
}
}
}

return -1;
}
``````
While this got Accepted running in 0.020 seconds:

Code: Select all

``````struct Node {
int x;
int y;
int z;
Node(int x = -1, int y = -1, int z = -1) : x(x), y(y), z(z) {};
};

int bfs(const vector< vector<string> >& map, const int L, const int H, const int W, const Node& beginning) {
queue<Node> toProcess;
toProcess.push(beginning);

vector< vector< vector<int> > > distance(L, vector< vector<int> >(H, vector<int>(W, -1)));
distance[beginning.x][beginning.y][beginning.z] = 0;

while(!toProcess.empty()) {
Node actual = toProcess.front(); toProcess.pop();
if(map[actual.x][actual.y][actual.z] == 'E') {
return distance[actual.x][actual.y][actual.z];
}
static const int dx[] = { 0, 0, 0, 0,-1, 1};
static const int dy[] = { 0, 0,-1, 1, 0, 0};
static const int dz[] = {-1, 1, 0, 0, 0, 0};
for(int i = 0; i < 6; ++i) {
int nx = actual.x + dx[i];
int ny = actual.y + dy[i];
int nz = actual.z + dz[i];
if(nx >= 0 && nx < L && ny >= 0 && ny < H && nz >=0 && nz < W && distance[nx][ny][nz] == -1 && map[nx][ny][nz] != '#') {
Node neighbor(nx, ny, nz);
distance[nx][ny][nz] = distance[actual.x][actual.y][actual.z] + 1;
toProcess.push(neighbor);
}
}
}

return -1;
}
``````
Notice that the only difference is that in the first code, the distance of the Node is an atribute while in the second the distance is stored in an array.

I have used the other code to succesfully solve other BFS problems with good running times so I don't know if the huge difference in times in this problem has something to do with the statement or is it that my first approach is really very slow.

What do you think?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: BFS

Well, vector<bool> can sometimes be painfully slow. gcc tries very hard to make it use only 1 bit per entry, and it's very non-straightforward to overload operator [] in C++ in this case - it involves returning proxy classes instead of a simple reference.

Try to replace vector<bool> with a static boolean array, vector<char>, or bitset.

abhi86
New poster
Posts: 1
Joined: Mon Oct 19, 2009 8:17 am

### Re: BFS

Hi all,
I am using a BFS and I get a TLE. I have seen that many users have solved it using simple BFS. Can anybody please help me out with my code.

Code: Select all

``````# include <iostream>
# include <cstdio>
# include <cstring>
# include <vector>
# include <queue>
# include <algorithm>

using namespace std;

struct maze_point
{
int x,y,l;
};

queue<maze_point> Q;
char maze[35][35][35];
int visited[35][35][35];
int dist[35][35][35];
maze_point startnode;
maze_point endnode;

int L,R,C;

void emptyq()
{
while(!Q.empty())
{
Q.pop();
}
}

void bfs()
{
int ql = 1,qp = 0;

visited[startnode.l][startnode.x][startnode.y]=1;

Q.push(startnode);

while(!Q.empty())
{
maze_point tmp = Q.front();
Q.pop();
visited[tmp.l][tmp.x][tmp.y]=1;

//	cout<<tmp.l<<' '<<tmp.x<<' '<<tmp.y<<endl;

if(maze[tmp.l][tmp.x][tmp.y] == 'E')
{
cout<<"Escaped in "<<dist[tmp.l][tmp.x][tmp.y]<<" minute(s)."<<endl;
return;
}

maze_point t;

//up
if(tmp.l-1>=0 && maze[tmp.l-1][tmp.x][tmp.y]!='#' && !visited[tmp.l-1][tmp.x][tmp.y])
{
t.x = tmp.x;
t.y = tmp.y;
t.l = tmp.l-1;
dist[tmp.l-1][tmp.x][tmp.y]=dist[tmp.l][tmp.x][tmp.y]+1;
Q.push(t);
}
//down
if(tmp.l+1<L && maze[tmp.l+1][tmp.x][tmp.y]!='#' && !visited[tmp.l+1][tmp.x][tmp.y])
{
t.x = tmp.x;
t.y = tmp.y;
t.l = tmp.l+1;
dist[tmp.l+1][tmp.x][tmp.y]=dist[tmp.l][tmp.x][tmp.y]+1;
Q.push(t);
}

t.l = tmp.l;
//north
if(tmp.x-1>=0 && maze[tmp.l][tmp.x-1][tmp.y]!='#' && !visited[tmp.l][tmp.x-1][tmp.y])
{
t.x = tmp.x-1;
t.y = tmp.y;
dist[tmp.l][tmp.x-1][tmp.y]=dist[tmp.l][tmp.x][tmp.y]+1;
Q.push(t);
}
//south
if(tmp.x+1<R && maze[tmp.l][tmp.x+1][tmp.y]!='#'&& !visited[tmp.l][tmp.x+1][tmp.y])
{
t.x = tmp.x+1;
t.y = tmp.y;
dist[tmp.l][tmp.x+1][tmp.y]=dist[tmp.l][tmp.x][tmp.y]+1;
Q.push(t);
}
//east
if(tmp.y+1<C && maze[tmp.l][tmp.x][tmp.y+1]!='#' && !visited[tmp.l][tmp.x][tmp.y+1])
{
t.x = tmp.x;
t.y = tmp.y+1;
dist[tmp.l][tmp.x][tmp.y+1]=dist[tmp.l][tmp.x][tmp.y]+1;
Q.push(t);
}
//west
if(tmp.y-1>=0 && maze[tmp.l][tmp.x][tmp.y-1]!='#' && !visited[tmp.l][tmp.x][tmp.y-1])
{
t.x = tmp.x;
t.y = tmp.y-1;
dist[tmp.l][tmp.x][tmp.y-1]=dist[tmp.l][tmp.x][tmp.y]+1;
Q.push(t);
}

}

cout<<"Trapped!"<<endl;
}

int main()
{
//freopen("test","r",stdin);
while(cin>>L>>R>>C)
{

if(L == 0 && R == 0 && C == 0)
{
return 0;
}

emptyq();
memset(visited,0,sizeof(visited));
memset(dist,0,sizeof(dist));
memset(&startnode,0,sizeof(startnode));
memset(&endnode,0,sizeof(endnode));

for(int l = 0;l<L;l++)
{
for(int r = 0;r<R;r++)
{
scanf("%s",maze[l][r]);
for(int c = 0;c<C;c++)
{
if(maze[l][r][c] == 'S')
{
startnode.x = r;
startnode.y = c;
startnode.l = l;
dist[l][r][c]=0;
}
if(maze[l][r][c] == 'E'){
endnode.x = r;
endnode.y = c;
endnode.l = l;
dist[l][r][c]=0;
}
}
}
}

bfs();
}

return 0;
}

``````

Thanks