Bfs

[zero-impact]

I'm trying to learn BFS. My problem is I can't get it to find the destination in the shortest number of steps.

Input:
put this map in a file named 3.in

###############
#x......#o....#
#.......#.....#
#.......#.....#
#.............#
#.......#.....#
#.......#.....#
###############

c++:

#include <iostream> #include <fstream> #include <string> #include <queue> using namespace std; struct Vert {         char type;         int x;         int y; }; int main() {         ofstream fout ("3.out");         ifstream fin ("3.in");                 int dir [8] = {0,-1,1,0,0,1,-1,0};         int steps = 0;         Vert grid [15][8];         Vert start;         queue <Vert> next;         for (int y = 0; y < 8; y++)         {                 for (int x = 0; x < 15; x++)                 {                         fin >> grid [x][y].type;                         grid [x][y].x = x;                         grid [x][y].y = y;                         if (grid [x][y].type == 'x')                         {                                 start.x = x;                                 start.y = y;                         }                 }         }         next.push (start);         while (!next.empty())         {                 Vert current = next.front (); //dequeue a vert                 next.pop();                                 if (current.type == 'o')                 {                         steps++;                         cout << "Found in: " << steps << endl;                         break;                 }                 else                 { //enqueue neighbors                         for (int i = 0; i < 8; i += 2)                         {                                 if (grid [current.x + dir [i]] [current.y + dir [i + 1]].type != '#') // if it isnt taken                                 {                                         //grid [current.x + dir [i]] [current.y + dir [i + 1]].type = '#';                                         next.push(grid [current.x + dir [i]] [current.y + dir [i + 1]]); //add it to the queue                                 }                         }                         steps++;                         grid [current.x] [current.y].type = '#'; //make it vissited                 }                                                 /*for (int y = 0; y < 8; y++)                 {                         for (int x = 0; x < 15; x++)                         {                                 cout << grid [x][y].type;                         }                         cout << endl;                 }                 getchar ();*/         }         return 0; }

[A.J]

hmm....I can't seem to find anything obviously wrong with your code...

but what does your program output? and do you mind providing the actual map in a textcase (since the map you gave looks distorted).

did you surround the map with a wall initially? since when you add all the neighbours to a square near the border, you tend to add a square that os outside of the map...try surrounding the map with walls, so this problem doesn't occur.

[DemonWasp]

The problem doesn't appear to be with the core of the algorithm, but in that you are calculating "steps" incorrectly. What you're actually calculating for "steps" right now is something more like "number of vertices visited" - note that you increment steps by one for each vertex you visit, even if it's not part of the shortest path.

A correct implementation of a BFS requires that you track the step number at which each vertex was discovered. There are a number of ways of doing this, so I'll leave it up to you to determine exactly how.

[A.J]

(sry for the double IDENTICAL posts ....it was an accident)

k, I see the problem now

like DemonWasp has pointed out, your 'steps' should be a counter that records how 'deep' the BFS goes (i.e. how many generations of neighbours that were added to the queue)

right now, you are incrementing your counter for every neighbour that was added...that is different...

[zero-impact]

Ok thanks. I had a feeling that it was something like that. Also the map will appear correctly if you just copy and paste that into notepad.

[A.J]

does it work now?

[CodeMonkey2000]

The most commonly used method is to use an integer board that know how to get from the starting point to everywhere else on the map in the shortest amount of steps. So if table[0,0] is your starting point, table[i,j] holds the least number of steps to get vertex[i,j] from [0,0].


And imo, the vert structure makes your code unnecessarily complex.

[A.J]

CodeMonkey2000 wrote:

The most commonly used method is to use an integer board that know how to get from the starting point to everywhere else on the map in the shortest amount of steps. So if table[0,0] is your starting point, table[i,j] holds the least number of steps to get vertex[i,j] from [0,0].


And imo, the vert structure makes your code unnecessarily complex.

well, the easiest way imo, is using a queue (in C++, since turing doesnt have queues) and keep pusing adjacent squares into the queue

it is easy to code AND simple

[DemonWasp]

Turing may get queues soon, if you'd like, see here

But yes, CodeMonkey is correct - the best implementation is probably a queue to hold the "current" set and an int** for the grid, with flag values for start-point, end-point and wall.

[A.J]

DemonWasp wrote:

Turing may get queues soon, if you'd like, see here

But yes, CodeMonkey is correct - the best implementation is probably a queue to hold the "current" set and an int** for the grid, with flag values for start-point, end-point and wall.

well, I guess you could code you own queue in turing....

as for the bfs, yea, thats what I said too..have a queue to store the set of neighbors that were added..but I find surrounding the map with walls initially avoids you from error checking for the added neighbors (i.e. if the square is outside the map, then you don't add it...so either you make sure the row and column is within range of the map's row and column, or just merely surround the map by walls)