Computer Science Canada

Tree's, and Maze type problems

Author:  Panphobia [ Mon Nov 05, 2012 1:31 pm ]
Post subject:  Tree's, and Maze type problems

I am interested in learning about how to solve problems involving trees and maze type questions like this(http://dwite.org/questions/ice_maze.html), i am wondering where i can find a tutorial for these. If you could link me to some that would be dandy, Thanks Smile

Author:  crossley7 [ Mon Nov 05, 2012 4:38 pm ]
Post subject:  RE:Tree\'s, and Maze type problems

Here are a few things that you can look up and try implementing (Google can be your best friend). I will try to order them in order of increasing difficulty.

Breadth First Search
Floyd-Warshall Algorithm
Bellman-Ford Algorithm
Prim's Algorithm
Dijkstra's algorithm

These are ones I have found are generally will get most of those types of problems. Though often you need a small twist to the algorithm or an understanding of how to apply it. There are also many other options out there but I have not coded them so cannot comment on how they work or the difficulty in implementing and efficiency.

Author:  Panphobia [ Mon Nov 05, 2012 5:33 pm ]
Post subject:  RE:Tree\'s, and Maze type problems

So like can you give me an example, I only need one, so like the breadth first search can you use it with this http://dwite.org/questions/trick_or_treeing.html

Author:  Tony [ Mon Nov 05, 2012 7:10 pm ]
Post subject:  RE:Tree\'s, and Maze type problems

Yes. Although that particular question is even easier, as the solution is derived from the height of the tree, which you can obtain via counting the parenthesis in the input line.

Author:  Panphobia [ Mon Nov 05, 2012 8:26 pm ]
Post subject:  Re: Tree's, and Maze type problems

is this good O:
code:
int total = 0;

        String nextTotal = "";
        StringTokenizer str;

        while (s.hasNext()) {
            total = 0;
            int height1 = 0;
            int max = 0;
            int height = 0;
            nextTotal = "";
            String line = s.nextLine();
            for (int i = 0; i < line.length(); i++) {
                if (line.charAt(i) != ')' && line.charAt(i) != '(') {
                    nextTotal += line.charAt(i);
                }
            }
            str = new StringTokenizer(nextTotal);
            while (str.hasMoreTokens()) {
                total += Integer.parseInt(str.nextToken());

            }
            for (int i = 0; i < line.length(); i++) {
                if (line.charAt(i) == '(') {
                    height++;
                    height1++;
                    max = Math.max(height, max);
                } else if (line.charAt(i) == ')') {
                    height--;
                }
            }
            out.println(((height1 * 4) - max) + " " + total);
        }
        out.close();

Author:  Tony [ Mon Nov 05, 2012 11:53 pm ]
Post subject:  RE:Tree\'s, and Maze type problems

test cases are available at http://dwite.org/home/testcase/231 so test out and see if your output matches the expected results.


: