graph - C++: Using BFS to find a path through a matrix -

suppose 1 given matrix

1 1 0 0 0

0 1 1 0 0

1 0 1 1 0

0 1 1 0 0

0 0 1 1 1

and asked find path only passing through ones top-left point (bold italic 1) bottom-right point (another similar 1). once such path shown in bold.

i have been trying implement in c++, i'm - surprise - segfaulting. more importantly, can't work out way without duplicating lot of code.

here code:

#include <iostream> #include <vector> #include <map> #include <queue> #include <algorithm> #include <list>  using namespace std;  typedef pair<int, int> coords;  struct point {     int x, y;     int val;     bool visited;     point (int a, int b, int v) : x(a), y(b), val(v), visited(false) {} };  int main() {     int n;     cin >> n;      vector<vector<point> > pts(n, vector<point>(n, point(0, 0, 0)));     int temp = 0;     for(int = 0; < n; ++i) {         for(int j = 0; j < n; ++j) {             cin >> temp;             pts[i][j] = point(i, j, temp);         }     }      queue<coords> tovisit;      tovisit.push(coords(0,0));     coords cur(0, 0);     vector<coords> neighbors;      while(!tovisit.empty()) {         cur = tovisit.back();         tovisit.pop();         int x = cur.first, y = cur.second;         pts[x][y].visited = true;          bool xgt0 = x > 0, xltm = x < n;         bool ygt0 = y > 0, yltm = y < n;          //  x-1,y-1 x  ,y-1 x+1,y-1         //  x-1,y   x  ,y   x+1,y         //  x-1,y+1 x  ,y+1 x+1,y+1          if(xgt0) {                     if(!pts[x-1][y].visited)   tovisit.push(coords(x-1,y));             if(ygt0 && !pts[x-1][y-1].visited) tovisit.push(coords(x-1,y-1));             if(yltm && !pts[x-1][y+1].visited) tovisit.push(coords(x-1,y+1));         }          if(ygt0 && !pts[x][y-1].visited) tovisit.push(coords(x,y-1));         if(yltm && !pts[x][y+1].visited) tovisit.push(coords(x,y+1));          if(xltm) {                     if(!pts[x+1][y].visited)   tovisit.push(coords(x+1,y));             if(ygt0 && !pts[x+1][y-1].visited) tovisit.push(coords(x+1,y-1));             if(yltm && !pts[x+1][y+1].visited) tovisit.push(coords(x+1,y+1));         }     }      for(int = 0; < n; ++i) {         for(int j = 0; j < n; ++j) {             cout << pts[i][j].visited << " ";         }         cout << endl;     } } 

it doesn't work @ all. how go fixing this?

and how write program without duplicating code in bfs neighbour-addition segment?

---

edit

solved, here code (which solves original problem).

a little bit of refactoring done decrease code duplication, more done, example turning if(something && proceed(...)) push(...) if(something) pushifok(...). left exercise adventurous reader little more time on hands @ moment. :)

#include <iostream> #include <vector> #include <map> #include <queue> #include <algorithm> #include <list>  using namespace std;  typedef pair<int, int> coords;  struct point {     int x, y;     bool val; //passable or not?     bool visited;     point (int a, int b, bool v) : x(a), y(b), val(v), visited(false) {} };  bool proceed(point);  int main() {     int n;     cin >> n;      vector<vector<point> > pts(n, vector<point>(n, point(0, 0, true)));     int temp = 0;     for(int = 0; < n; ++i) {         for(int j = 0; j < n; ++j) {             cin >> temp;             pts[i][j] = point(i, j, temp == 1);         }     }      queue<coords> tovisit;      tovisit.push(coords(0,0));     coords cur(0, 0);     vector<coords> neighbors;      while(!tovisit.empty()) {         cur = tovisit.back();         tovisit.pop();         int x = cur.first, y = cur.second;         pts[x][y].visited = true;          bool xgt0 = x > 0, xltm = x < n - 1;         bool ygt0 = y > 0, yltm = y < n - 1;          //  x-1,y-1 x  ,y-1 x+1,y-1         //  x-1,y   x  ,y   x+1,y         //  x-1,y+1 x  ,y+1 x+1,y+1          if(ygt0 && proceed(pts[x][y-1])) tovisit.push(coords(x,y-1));         if(yltm && proceed(pts[x][y+1])) tovisit.push(coords(x,y+1));          if(xgt0) {             if(proceed(pts[x-1][y])) tovisit.push(coords(x-1,y));             if(ygt0 && proceed(pts[x-1][y-1])) tovisit.push(coords(x-1,y-1));             if(yltm && proceed(pts[x-1][y+1])) tovisit.push(coords(x-1,y+1));         }          if(xltm) {             if(proceed(pts[x+1][y])) tovisit.push(coords(x+1,y));             if(ygt0 && proceed(pts[x+1][y-1])) tovisit.push(coords(x+1,y-1));             if(yltm && proceed(pts[x+1][y+1])) tovisit.push(coords(x+1,y+1));         }     }      for(int = 0; < n; ++i) {         for(int j = 0; j < n; ++j) {             cout << pts[i][j].visited << " ";         }         cout << endl;     } }  bool proceed(point p) { return p.val && !p.visited; } 

i have been trying implement in c++, i'm - surprise - segfaulting.

your problem segfaults due high value check:

if (yltm && !pts[x][y+1].visited) tovisit.push(coords(x,y+1)); 

note when y = n - 1 yltm == true , attempt access pts[x][n] entry in array, doesn't exist (its @ position n + 1, 0 based indexing , all).

unfortunately, due nature of input data, need check boundaries , have duplicated-looking code, don't think can avoid in case. hint after fix segfaulting , move on trying find actual path between corners: try keeping track of "depth" of search , use find path top left bottom right.