|
|
 |
|
|
Thread Tools | Display Modes |
|
|
Sep 18th, 2004, 9:35 AM
|
#1 |
|
The Supreme Ruler
 Join Date: May 2004
Location: Houston
Posts: 1,476
Rep Power: 6
 |
We got this problem yesterday. Our teacher said if we get it done before October he'll give us extra credit, but I don't really even know where to start. Just point me in the right direction por favor. Here's the problem:
Maze Surfing You dirty rat. You're caught in a malicious lab experiment, and dropped into a maze. Your job is to find the cheese and thereby to prove your superior intelligence of the various rodent sopecies. Program Input The input file PROG13.IN describes a single maze. The first line of the file is an integer, N, indicating the number of rows and columns in the maze, constrained by: 8 < N < 19. The next N lines each contain N characters seperated by spaces. Walls are represented by '#', hallways by '.', the start position by 'M' and the cheese by 'C'. Program Output The program should write the maze to PROG13.OUT, drawing the shortest path from M to C with a series of '+' characters. You may assume that (1) there will be a valid path from M to C, and (2) there will only be one path from M to C (i.e., no loops). The path is not permitted to contain any diagnol movements. Sample Input: 10 # # # # # # # # # # # . # M . . # . . # # . # # . # # # . # # . . . . . . . . # # # # # . # . # # # # . . . . # . # C # # # # # # # . # . # # . # . . . . # . # # . . . # . . . . # # # # # # # # # # # Sample Output: # # # # # # # # # # # . # M + . # . . # # . # # + # # # . # # . . . + + + . . # # # # # . # + # # # # . . . . # + # C # # # # # # # + # + # # . # . . . + # + # # . . . # . + + + # # # # # # # # # # #
__________________
"Every gun that is made, every warship launched, every rocket signifies, in the final sense, a theft from those who hunger and are not fed, from those who are cold and are not clothed. The world in arms is not spending money alone. It is spending the sweat of its laborers, the genius of its scientists, the hopes of its children." - Dwight D. Eisenhower |
|
|
|
Sep 18th, 2004, 1:54 PM
|
#2 |
|
I eat cake for breakfast.
Join Date: Jul 2004
Location: In my box.
Posts: 4,434
Rep Power: 9
|
I'm not sure how you're gonna do this, though I might work on it sometime - looks like a challenge
 Try this to get started: load the maze into a boolean array, with TRUE as the parts the rodent can move through, and FALSE as the parts it can't. Might help. |
|
|
|
|
Sep 18th, 2004, 2:04 PM
|
#3 |
|
The Supreme Ruler
Join Date: May 2004
Location: Houston
Posts: 1,476
Rep Power: 6
|
Yea. I've been thinking about using a 2-dimensional array. I did a little research on google, and decided that the depth-first search might work. Anyone have any other suggestions? Anyone have any examples they might be able to provide me of the depth-first search in action?
__________________
"Every gun that is made, every warship launched, every rocket signifies, in the final sense, a theft from those who hunger and are not fed, from those who are cold and are not clothed. The world in arms is not spending money alone. It is spending the sweat of its laborers, the genius of its scientists, the hopes of its children." - Dwight D. Eisenhower |
|
|
|
|
Sep 18th, 2004, 4:31 PM
|
#4 |
|
I eat cake for breakfast.
Join Date: Jul 2004
Location: In my box.
Posts: 4,434
Rep Power: 9
|
Depth-first? Can you provide a link?
|
|
|
|
|
Sep 18th, 2004, 5:27 PM
|
#5 |
|
The Supreme Ruler
Join Date: May 2004
Location: Houston
Posts: 1,476
Rep Power: 6
|
__________________
"Every gun that is made, every warship launched, every rocket signifies, in the final sense, a theft from those who hunger and are not fed, from those who are cold and are not clothed. The world in arms is not spending money alone. It is spending the sweat of its laborers, the genius of its scientists, the hopes of its children." - Dwight D. Eisenhower |
|
|
|
|
Sep 18th, 2004, 8:06 PM
|
#6 |
|
Hobbyist Programmer
Join Date: Apr 2004
Location: /dev/urandom
Posts: 154
Rep Power: 5
   |
I've looked at something like that with a friend. This was before I had really done any higher-level coding. We were trying to implement either a BFS or DFS in C using linked-lists to traverse the tree.
I think that this would work pretty well. It will not be optimal, as per the definition, but it should provide you with a working program. You would have to determine which nodes you could visit from the current (the 2D array would help there) and follow them. I like the DFS > BFS in this case because you will traverse a whole path before starting on the next, rather than traversing each path at the same time. Good luck!
__________________
"Time is an illusion. Lunchtime doubly so." -the late, great Douglas Adams |
|
|
|
|
Sep 18th, 2004, 10:40 PM
|
#7 |
|
Programming Guru
Join Date: Jul 2004
Location: United States
Posts: 3,467
Rep Power: 8
 |
Ahhh. The good ole school days... I remeber these.
use a two dimensional array and just comparisons for each elements value... a link list would be nice, but no need for the complexity, should be a fairly simple solution.
__________________
http://jasonpowers.net "There are a thousand hacking at the branches of evil to one who is striking at the root." |
|
|
|
|
Sep 18th, 2004, 11:12 PM
|
#8 |
|
Programming Guru
Join Date: Jul 2004
Location: United States
Posts: 3,467
Rep Power: 8
|
Mjordan2nd: Show us the code you have... where you are having problems, etc. I need to at least see a little bit of effort, so I don't ream ya for posting a straight-up homework assignment.
Multi-dimensional arrays to hold the map and element comparisons... and a stack to hold valid paths would solve the problem... when the cheese is found, you could output the stack as you pop the elements... or more specifically use the popped values to insert a '+' into the multidimensional array along the valid path and reprint the map. I'll probably do this, just for kicks... if I have time. But for you to learn it better, I need you to try it first and let me know where you are having problems.
__________________
http://jasonpowers.net "There are a thousand hacking at the branches of evil to one who is striking at the root." |
|
|
|
|
Sep 18th, 2004, 11:42 PM
|
#9 |
|
The Supreme Ruler
Join Date: May 2004
Location: Houston
Posts: 1,476
Rep Power: 6
|
Well, actually, when I asked, I didn't have anything done, quite honestly. I was having trouble visualizing how it would be done, but I think I have it figured out now. The way I plan on doing it is as follows:
I will set the starting position as the mouse as 1. Walls will be -1, and dots will be 0. For every spot there is a 0 next to the 1, it will be marked a 2. Every 2 that has a 0 next to it will get a 3 marked in that spot, and so on until I find the cheese. Once the cheese is found, I will just count backwards, and get all the pluses in, thereby showing the route to the cheese. Here's a visual representation of what I plan to do. [code] # # # # # # # # # # # . # 1 . . # . . # # . # # . # # # . # # . . . . . . . . # # # # # . # . # # # # . . . . # . # . # # # # # # # . # . # # . # . . . . # . # # . . . # . . . . # # # # # # # # # # # # # # # # # # # # # # . # 1 2 . # . . # # . # # . # # # . # # . . . . . . . . # # # # # . # . # # # # . . . . # . # . # # # # # # # . # . # # . # . . . . # . # # . . . # . . . . # # # # # # # # # # # # # # # # # # # # # # . # 1 2 3 # . . # # . # # 3 # # # . # # . . . . . . . . # # # # # . # . # # # # . . . . # . # . # # # # # # # . # . # # . # . . . . # . # # . . . # . . . . # # # # # # # # # # # # # # # # # # # # # # . # 1 2 3 # . . # # . # # 3 # # # . # # . . . 4 . . . . # # # # # . # . # # # # . . . . # . # . # # # # # # # . # . # # . # . . . . # . # # . . . # . . . . # # # # # # # # # # # # # # # # # # # # # # . # 1 2 3 # . . # # . # # 3 # # # . # # . . 5 4 5 . . . # # # # # 5 # . # # # # . . . . # . # . # # # # # # # . # . # # . # . . . . # . # # . . . # . . . . # # # # # # # # # # # # # # # # # # # # # # . # 1 2 3 # . . # # . # # 3 # # # . # # 7 6 5 4 5 6 7 . # # # # # 5 # 7 # # # # . . 7 6 # . # . # # # # # # # . # . # # . # . . . . # . # # . . . # . . . . # # # # # # # # # # # # # # # # # # # # # # . # 1 2 3 # . . # # 8 # # 3 # # # . # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # . 8 7 6 # 8 # . # # # # # # # . # . # # . # . . . . # . # # . . . # . . . . # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # . . # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # . # # # # # # # 9 # . # # . # . . . . # . # # . . . # . . . . # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # . A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # . # # # # # # # 9 # . # # . # . . . A # . # # . . . # . . . . # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # . # # # # # # # 9 # . # # . # . . B A # . # # . . . # . B . . # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # . # # # # # # # 9 # . # # . # . C B A # . # # . . . # C B C . # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # . # # # # # # # 9 # . # # . # D C B A # . # # . . . # C B C D # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # . # # # # # # # 9 # . # # . # D C B A # E # # . . E # C B C D # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # . # # # # # # # 9 # F # # . # D C B A # E # # . F E # C B C D # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 #10 # # # # # # # 9 # F # # . # D C B A # E # #10 F E # C B C D # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # + # # # # # # # 9 # F # # . # D C B A # E # #10 F E # C B C D # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # + # # # # # # # 9 # + # # . # D C B A # E # #10 F E # C B C D # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # + # # # # # # # 9 # + # # . # D C B A # + # #10 F E # C B C D # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # + # # # # # # # 9 # + # # . # D C B A # + # #10 F E # C B C + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # + # # # # # # # 9 # + # # . # D C B A # + # #10 F E # C B + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # + # # # # # # # 9 # + # # . # D C B A # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # + # # # # # # # 9 # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # + # # # # # # # + # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # + # + # # # # # # # + # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # + # # # # 9 8 7 6 # + # + # # # # # # # + # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 + 7 8 # # # # # 5 # + # # # # 9 8 7 6 # + # + # # # # # # # + # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 + + 7 8 # # # # # 5 # + # # # # 9 8 7 6 # + # + # # # # # # # + # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 + + + 7 8 # # # # # 5 # + # # # # 9 8 7 6 # + # + # # # # # # # + # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # + # # # 9 # # 7 6 5 + + + 7 8 # # # # # 5 # + # # # # 9 8 7 6 # + # + # # # # # # # + # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 + 3 # B A # # 8 # # + # # # 9 # # 7 6 5 + + + 7 8 # # # # # 5 # + # # # # 9 8 7 6 # + # + # # # # # # # + # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # + + 3 # B A # # 8 # # + # # # 9 # # 7 6 5 + + + 7 8 # # # # # 5 # + # # # # 9 8 7 6 # + # + # # # # # # # + # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # . # M + . # . . # # . # # + # # # . # # . . . + + + . . # # # # # . # + # # # # . . . . # + # C # # # # # # # + # + # # . # . . . + # + # # . . . # . + + + # # # # # # # # # # # Thanks for all the responses guys. Hopefully I'll show you guys my finished code tomorrow.
__________________
"Every gun that is made, every warship launched, every rocket signifies, in the final sense, a theft from those who hunger and are not fed, from those who are cold and are not clothed. The world in arms is not spending money alone. It is spending the sweat of its laborers, the genius of its scientists, the hopes of its children." - Dwight D. Eisenhower |
|
|
|
|
Sep 19th, 2004, 3:49 AM
|
#10 |
|
Programming Guru
Join Date: Jul 2004
Location: United States
Posts: 3,467
Rep Power: 8
|
Its 3:44am. I wrote a human-interactive version of this program.... approx. 317 lines of code, I did it the hard way, without using any fancy data structures... just nested if statements and while loops, etc.
If you need it to have "AI"... then I can put that in... it shouldn't be that difficult to do. For example: Here is part of my MoveMouse function that takes the mouse left: if (direction == "LEFT" || direction == "l" || direction == "L")
{
if (myMaze.mLocX == 0)
cout << "LEFT: Mouse hit boundary wall. Going back." << endl;
if (myMaze.grid[myMaze.mLocX][myMaze.mLocY-1] == "#")
cout << "LEFT: Mouse hit internal wall. Going back." << endl;
if (myMaze.grid[myMaze.mLocX][myMaze.mLocY-1] == ".")
{
myMaze.grid[myMaze.mLocX][myMaze.mLocY] = ".";
myMaze.grid[myMaze.mLocX][myMaze.mLocY-1] = "M";
myMaze.mLocY = myMaze.mLocY - 1;
cout << "LEFT: Mouse moves left." << endl;
}
if (myMaze.grid[myMaze.mLocX][myMaze.mLocY-1] == "C")
{
myMaze.grid[myMaze.mLocX][myMaze.mLocY-1] = "M";
cout << "LEFT: Mouse found cheese!" << endl;
}
}
__________________
http://jasonpowers.net "There are a thousand hacking at the branches of evil to one who is striking at the root." |
|
|
|
|
| Bookmarks |
| Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
| Thread Tools | |
| Display Modes | |
|
|
Hybrid Mode
