c++ - Breadth First Search using array -


i trying implement breadth first search maze using arrays. problem i'm facing cant expand paths @ same time. this:

####### 123456# #3###7# #4###8# #5###9g #######

the method i'm using using loop loop through array. set starting point c (current) , end point g (goal). when iterate through maze, search array location store character 'c'. checked if up, down, left, right wall. if not, i'll moved next bracket. new bracket set 'c' , previous bracket set 'o'.

for (int = 1; < 12; i++)     {         (int j = 0; j < 12; j++)         {             // find current node             if (maze[i][j] == 'c')             {              if (maze[i][j-1] == ' ')       //                 {                     maze[i][j-1] = 'c';                     maze[i][j] = 'o';                 }                  else if (maze[i][j+1] == ' ')       // down                 {                     maze[i][j+1] = 'c';                     maze[i][j] = 'o';                 }                  else if (maze[i-1][j] == ' ')       // left                 {                     maze[i-1][j] = 'c';                     maze[i][j] = 'o';                 }                 else if (maze[i+1][j] == ' ')                 {                     maze[i+1][j] = 'c';                     maze[i][j] = 'o';                      }     }

how implement part 'c' bracket @ junction? using loop keep coming out this:

#######   #######   #######   #######  #######  #######  #######  ####### c     #   oc    #   ooc   #   oooc  #  ooooc #  oooooc#  oooooo#  oooooo# # ### #   # ### #   #c### #   #c### #  #c### #  #c### #  #o###c#  #o###o# # ### #   # ### #   # ### #   # ### #  # ### #  # ### #  #c### #  #o###c# # ###     # ###     # ###     # ###    # ###    # ###    # ###    #c###  #######   #######   #######   #######  #######  #######  #######  #######

in general, don't literally expand paths simultaneously in bfs. instead, put first element queue, , iteratively pop first element front , add elements of queue reachable element , not contained in queue already.

you trying work on map only; not possible bfs. need queue contains positions of visited elements , way mark elements done.

http://en.wikipedia.org/wiki/breadth-first_search has nice example that.


Comments

Post a Comment

Popular posts from this blog

android - Get AccessToken using signpost OAuth without opening a browser (Two legged Oauth) -

i using signpost oauth access data magento server. have read various tutorials on same , reach point open browser user can enter credentials. however, per requirement have automate part. hence, user should not browser page. have set-up done on server side ( magento ), hit url , returned call page. same through program in android. i have tried below, consumer = new commonshttpoauthconsumer(key, secret); provider = new commonshttpoauthprovider(oauth_init_url,access_token_url, authorize_url); try { provider.retrieverequesttoken(consumer, oauth.out_of_band); log.d("tokens" , consumer.gettoken() + " -- " + consumer.gettokensecret()); } and request tokens. dont know how bypass next step. tried directly accessing accesstoken (stupid of me) provider.retrieveaccesstoken(consumer, "mycallback://callback"); no luck, ends in oauth.signpost.exception.oauthnotauthorizedexception: authorization failed (server replied 401). ...
Read more

org.mockito.exceptions.misusing.InvalidUseOfMatchersException: mockito -

getting error org.mockito.exceptions.misusing.invaliduseofmatchersexception: invalid use of argument matchers! 1 matchers expected, 2 recorded. exception may occur if matchers combined raw values: //incorrect: somemethod(anyobject(), "raw string"); when using matchers, arguments have provided matchers. example: //correct: somemethod(anyobject(), eq("string matcher")); at when( getprogramservice .callservice(any(getprogramtype.class))) .thenreturn(jaxbresponse); please explain error , possible resolution the code posted looks fine; don't see problem it. code before or above causing exception. key here: invalid use of argument matchers! 1 matchers expected, 2 recorded. any , used above, doesn't return "special kind of null" or "special kind of getprogramtype"; don't exist. instead, returns null , side effect puts matcher on stack. whe...
Read more

google shop client API returns 400 bad request error while adding an item -

i'm working on solution add items in google shopping market java application. following tutorial real mess because of missing classes of laste release, after setting 1.5-beta maven managed make base example typecheck correctly classes. still can make simple task of adding 1 item. instead of posting whole code i'm posting part creates product feed. private product createproduct(string id) { product product = new product(); product.title = "red wool sweater"; product.content = new content( "text", "comfortable , soft, sweater keep warm on " + "cold winter nights. red , blue stripes."); product.appcontrol = new appcontrol(); product.appcontrol.addrequireddestination("productads"); product.externalid = id; product.lang = "it"; product.country = "it"; product.condition = "nuovo"; product.price = new price("eu...
Read more