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.


Comments

Post a Comment

Popular posts from this blog

python - mat is not a numerical tuple : openCV error -

-
i have write down code showing error ma not getting it: please help: showing mat not numerical tuple: import cv import cv2 capture = cv2.videocapture("j.3gp") while(1): _, frame1 = capture.read() grayimage1 = cv2.cvtcolor(frame1, cv2.color_bgr2gray) _, frame2 = capture.read() grayimage2 = cv2.cvtcolor(frame2, cv2.color_bgr2gray) differenceimage = cv2.absdiff(grayimage1,grayimage2) thresholdimage = cv2.threshold(differenceimage,25,255,cv2.thresh_binary) cv2.imshow("difference image", differenceimage) cv2.imshow("threshold image", thresholdimage) cv2.imshow("image", frame1) k = cv2.waitkey(30) & 0xff error arising : ----------------------------------------------------------------------------------------- traceback (most recent call last): file "desk.py", line 15, in <module> cv2.imshow("threshold image", thresholdimage) typeerror: mat not numerical tuple ...
Read more

c# - MSAA finds controls UI Automation doesn't -

-
i'm working on automating windows application. i'm using teststack white framework. i've hit problem. program has 'window' object cannot see inside of. white shows no controls inside of it. inspect.exe shows no controls inside of either when running in ui automation mode. if switch inspect msaa see controls inside fine. there anyway me use msaa c# handle on these controls? if can identify msaa functions need, can use p/invoke call them c#. here's example article doing msaa: http://www.codeproject.com/articles/38906/ui-automation-using-microsoft-active-accessibility also, pinvoke.net can used identify iaccessible (msaa) functions: http://www.pinvoke.net/search.aspx?search=iaccessible&namespace=[all] here's answer along lines: msaa com-based? finally, alternative p/invoke, might able use tlbimp.exe create wrapper assembly oleacc.dll, , access msaa functions through it. i'm not sure if works msaa, it's worth try. as e...
Read more

wordpress - .htaccess: RewriteRule: bad flag delimiters -

-
pulling hair out on one. have following .htaccess file custom redirects in addition wordpress's default settings. when tested on local wamp server worked fine after moving production i'm not getting rewriterule: bad flag delimiters error in server log , after while site goes down internal server error any appreciated. in advance! <ifmodule mod_rewrite.c> rewriteengine on rewritebase / rewriterule ^rockford_weddings___welcome\.html$ /wedding/ [r=301,l] rewriterule ^blog/?$ /journal/ [r=301,l] rewriterule ^blog/(.*)$ /$1 [r=301,l] rewriterule ^portraitinvestment/?$ /portraitinvestment\.pdf [r=301,l] rewriterule ^weddinginvestment/?$ /weddinginvestment\.pdf [r=301,l] rewriterule ^holidaycards2014/?$ /holidaycards2014\.pdf [r=301,l] </ifmodule> # begin wordpress <ifmodule mod_rewrite.c> rewriteengine on rewritebase / rewriterule ^index\.php$ - [l] rewritecond %{request_filename} !-f rewritecond %{request_filename} !-d rewriterule . /index.php [l] </...
Read more