-----------------------------------

Panphobia

Mon Nov 05, 2012 1:31 pm


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


-----------------------------------

crossley7

Mon Nov 05, 2012 4:38 pm


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.


-----------------------------------

Panphobia

Mon Nov 05, 2012 5:33 pm


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


-----------------------------------

Tony

Mon Nov 05, 2012 7:10 pm


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.


-----------------------------------

Panphobia

Mon Nov 05, 2012 8:26 pm


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();[/code]


-----------------------------------

Tony

Mon Nov 05, 2012 11:53 pm


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.