Wrox Programmer Forums

Need to download code?

View our list of code downloads.

Go Back   Wrox Programmer Forums > C# and C > C++ and Visual C++ > C++ Programming
Password Reminder
Register
| FAQ | Members List | Calendar | Search | Today's Posts | Mark Forums Read
C++ Programming General discussions for the C++ language. For questions specific to Microsoft's Visual C++ variant, see the Visual C++ forum instead.
Welcome to the p2p.wrox.com Forums.

You are currently viewing the C++ Programming section of the Wrox Programmer to Programmer discussions. This is a community of tens of thousands of software programmers and website developers including Wrox book authors and readers. As a guest, you can read any forum posting. By joining today you can post your own programming questions, respond to other developers’ questions, and eliminate the ads that are displayed to guests. Registration is fast, simple and absolutely free .
DRM-free e-books 300x50
Reply
 
Thread Tools Search this Thread Display Modes
  #1 (permalink)  
Old August 2nd, 2003, 04:16 PM
Registered User
 
Join Date: Aug 2003
Location: , , .
Posts: 1
Thanks: 0
Thanked 0 Times in 0 Posts
Default a question

Hello!
I want to write a program about tracing.
We have a 5*5 coulumn with a few black blanks.
We want to move from left sided in below of coulumn
and go to right sided in above of coulumn and we mustnot
move across black blanks.
We want the simplest and shortest way .
I hope you help me.
Thank you.
regards.

Reply With Quote
  #2 (permalink)  
Old August 9th, 2003, 03:44 PM
Authorized User
 
Join Date: Jun 2003
Location: , , USA.
Posts: 83
Thanks: 0
Thanked 0 Times in 0 Posts
Send a message via ICQ to natmaster Send a message via AIM to natmaster Send a message via MSN to natmaster
Default

i don't know if this is the most efficient way, but one of the easy ways of doing this, are to write a program that would go through all the possibilities, then store them in an array, along with the number of moves it took (probably want to make a class for this). then, do a check to see which one is the smallest.


here's an example of the data members, but i won't write all the code for u:

class route {
private:
 int moves;
 coords *routeHead; //linked list of the directions it took
}

class coords {
private:
 int x;
 int y;
}


to go through each possibility, have a recursive function that checks to see if it can go in each direction, if it can, it calls itself. base case is it reaches the end of the maze, or it can't go anywhere but back. while it does this, it records the data into the class.

----------------------------
http://aeonofdarkness.com
Reply With Quote
  #3 (permalink)  
Old August 11th, 2003, 07:41 AM
Authorized User
 
Join Date: Jun 2003
Location: Gainesville, FL, USA.
Posts: 25
Thanks: 0
Thanked 0 Times in 0 Posts
Default

natmaster is suggesting a Depth-First Search. Looking at the brief description of the problem, I'd go for a Breadth First approach, wioth a recursive fn:
Solve Routine:
==============
LET v be a set (ArrayList, Hashtable, what-have-you);
Add the starting board configuration to v;
RETURN the result of doit(v, 0);

doit Routine:
=============
Parameters:
edge: a set (ArrayList, Hashtable, what-have-you) of the current possible position(s);
n: the number of moves done so far;

LET nextEdge be an empty set;
FOREACH boardConfiguration in edge:
  IF the boardConfiguration is the goal
    RETURN n;
  LET children be the set of board configuration that may be created from boardConfiguration
  by applying all the possible moves;
  ADD to nextEdge all the element of children;
LET nn be n+1;
RETURN doit(nextEdge, nn);

HTH,
Olorin
Reply With Quote
Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Trackbacks are Off
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
question maheshraju ASP.NET 2.0 Basics 3 March 13th, 2008 08:54 AM
Question Ashwini Classic ASP Databases 3 January 10th, 2006 07:20 AM
Question Ashwini Classic ASP Databases 1 January 4th, 2006 06:55 AM
Question? Calibus Classic ASP Databases 8 August 6th, 2004 08:25 AM



All times are GMT -4. The time now is 10:45 AM.


Powered by vBulletin®
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
© 2013 John Wiley & Sons, Inc.