BFS

Let's talk about algorithms!

Moderator: Board moderators

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

BFS

Post by slxst » Tue Apr 28, 2009 12:32 am

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

Post by mf » Tue Apr 28, 2009 2:10 am

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

Post by abhi86 » Mon Oct 19, 2009 8:20 am

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

Post Reply

Return to “Algorithms”