Wrox Programmer Forums
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 software programmers and website developers including Wrox book authors and readers. New member registration was closed in 2019. New posts were shut off and the site was archived into this static format as of October 1, 2020. If you require technical support for a Wrox book please contact http://hub.wiley.com
  #1 (permalink)  
Old August 2nd, 2003, 04:16 PM
Registered User
Join Date: Aug 2003
Posts: 1
Thanks: 0
Thanked 0 Times in 0 Posts
Default a question

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.

Reply With Quote
  #2 (permalink)  
Old August 9th, 2003, 03:44 PM
Authorized User
Join Date: Jun 2003
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

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 {
 int moves;
 coords *routeHead; //linked list of the directions it took

class coords {
 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.

Reply With Quote
  #3 (permalink)  
Old August 11th, 2003, 07:41 AM
Authorized User
Join Date: Jun 2003
Posts: 25
Thanks: 0
Thanked 0 Times in 0 Posts

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:
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);

Reply With Quote

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

Powered by vBulletin®
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.
Copyright (c) 2020 John Wiley & Sons, Inc.