Programming Forums - Need A Little Help

Programming Forums (http://www.programmingforums.org/forumindex.php)

- Java (http://www.programmingforums.org/forum17.html)

- - Need A Little Help (http://www.programmingforums.org/showthread.php?t=583)

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 #

# # # # # # + # + #

# . # . . . + # + #

# . . . # . + + + # 

# # # # # # # # # #

I'm not sure how you're gonna do this, though I might work on it sometime - looks like a challenge :D

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.

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?

Depth-first? Can you provide a link?

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!

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.

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.

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.

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;

    }

  }