Computer Science Canada

Help question
Author:  Panphobia [ Fri Dec 21, 2012 10:25 pm ]
Post subject:  Help question
Since the next 2 dwites have been canceled i have just been doing all the questions, and I hope to do them all during the winter break, I have had one problem with this question http://dwite.org/questions/haunted_house.html , I will explain what i think is wrong, when a map like this
code:
.......
.##a##.
.#***#.
.##B##.
.#*###.
.#*d*#.
#*#....
comes along, you have to stray from the shortest path in order to get the other candies, but my program counts the candies but not the path that they take, if they are not in the shortest path that is, here is my code, if you just hint me to the problem I will definetely be able to fix it
code:
import java.util.*;
import java.io.*;

public class BFSDFSV4 {
    static int n1 = -1, candy3 = 0, cCount = 0;
    static int MIN;
    static int candy=0;
    public static void main(String[] args) throws IOException {
        Scanner q = new Scanner(new File("C:\\Users\\branko\\Desktop\\Java\\BFSDFSV4\\src\\bfsdfsv4\\DATA5.txt"));
        for (int a = 0; a < 5; a++) {
            cCount = 0;
            candy=0;
            candy3 = 0;
            int startX = -1, startY = -1;
            char maze[][];
            n1 = Integer.parseInt(q.nextLine());
            maze = new char[n1][n1];
            for (int i = 0; i < n1; i++) {
                String s = q.nextLine();
                for (int j = 0; j < n1; j++) {
                    if (s.charAt(j) == 'B') {
                        startX = i;
                        startY = j;
                    }
                    if (s.charAt(j) == '*') {
                        cCount++;
                    }
                    maze[i][j] = s.charAt(j);
                }
            }
            MIN=0;
           // traverse(startX, startY, maze, 0, 0);
            int lol = bfs(maze,startX,startY);
            System.out.println(candy +" "+lol);
        }
    }
    //need to tweak
    public static int bfs(char[][]maze,int xStart,int yStart){
       
        Queue <int[]>queue = new LinkedList<int[]>();
        int[] start = {xStart,yStart,0};
        queue.add(start);
        while(queue.peek()!=null){
            int[]array=queue.remove();
            int x=array[0];int y=array[1];int steps=array[2];
            if(x>n1-1||y>n1-1||x<0||y<0)continue;
            if(maze[x][y]=='#')continue;
           
            if(maze[x][y]=='*'){
                MIN=array[2];
                candy++;
                maze[x][y]='.';

//                if(candy==1&&maze[x][y]=='a')
//                    maze[x][y]='.';
//                if(candy==2&&maze[x][y]=='b')
//                    maze[x][y]='.';
//                if(candy==3&&maze[x][y]=='c')
//                    maze[x][y]='.';
//                if(candy==4&&maze[x][y]=='d')
//                    maze[x][y]='.';
//                if(candy==5&&maze[x][y]=='e')
//                    maze[x][y]='.';
//                if(candy==6&&maze[x][y]=='f')
//                    maze[x][y]='.';
               
            }
            if(candy>cCount){
                candy = cCount;
                return MIN;
            }
            if(maze[x][y]>='a'&&maze[x][y]<='f'){
               // System.out.println(maze[x][y]-'a'+" "+candy);
                if(candy<maze[x][y]-'a'+1){
                    return MIN;
                }
            }
            int newPoints[][]={{0,1},{0,-1},{1,0},{-1,0}};
            for(int i = 0; i < 4;++i){
                int[]sta={x+newPoints[i][0],y+newPoints[i][1],array[2]+1};
                queue.add(sta);
            }
            maze[x][y]='#';
        }
        return MIN;
    }
}
Author:  Panphobia [ Wed Dec 26, 2012 9:39 pm ]
Post subject:  RE:Help question
what I am really asking is, is there a way to make a bfs not give you the shortest path, but the optimal path with your restrictions?
Author:  Tony [ Wed Dec 26, 2012 10:46 pm ]
Post subject:  RE:Help question
The shorted path _is_ the optimal path.
Quote:

The output file OUT5.txt will contain 5 lines of output, each a pair of non-negative integers C and S. C is the maximum number of candy pieces that Billy can collect. S is the minumum number of steps to do so.


The tricky part to this question is that as you collect candy, new nodes and edges appear in the graph.

In the example that you give, the answer would be the same event if all the doors were open spaces instead (so regular BFS).
Author:  Panphobia [ Thu Dec 27, 2012 12:53 am ]
Post subject:  RE:Help question
What I meant by shortest path was the path without counting in candies on the way, and by optimal I meant the path with all attainable candies
Author:  Panphobia [ Thu Dec 27, 2012 2:06 am ]
Post subject:  Re: Help question
would you guys tell me if I am overthinking it? now I have changed what i store in the queue, and the return value of my bfs, what I am trying to do now, is flood through the possible candies and figure out how many there are, and THEN, store the number of start points, call the bfs with the current start positions, and accumulate the shortest path to each candy, so basically i start at B and then I get the shortest path to the nearest candy, mark that position as visited, set the steps to 0, and then make the point where you found the candy, your new start point and check for the closest star from there, and then so on, for all of the possible candies, here is my code
code:
package bfsdfsv4;

import java.util.*;
import java.io.*;

public class BFSDFSV4 {

    static int n1 = -1, candy3 = 0, cCount = 0;
    static int MIN;
    static int mini[];
    //static int candy = 0;
    static int[][] MINs;
    static int totCandies = 0;

    public static void main(String[] args) throws IOException {
        Scanner q = new Scanner(new File("C:\\Users\\branko\\Desktop\\Java\\BFSDFSV4\\src\\bfsdfsv4\\DATA5.txt"));
        for (int a = 0; a < 5; a++) {
            cCount = 0;
            //candy = 0;
            candy3 = 0;
            int startX = -1, startY = -1;
            char maze[][];
            n1 = Integer.parseInt(q.nextLine());
            maze = new char[n1][n1];
            MINs = new int[n1][n1];
            for (int i = 0; i < n1; i++) {
                String s = q.nextLine();
                for (int j = 0; j < n1; j++) {
                    if (s.charAt(j) == 'B') {
                        startX = i;
                        startY = j;
                    }
                    if (s.charAt(j) == '*') {
                        cCount++;
                    }
                    maze[i][j] = s.charAt(j);
                    //MINs[i][j] = 9999;
                }
            }
            //mini = new int[100];
            // for (int i = 0; i < 100; ++i) {
            //     mini[i] = 0;
            //}
            MIN = 0;
            // MIN=99999;
            // traverse(startX, startY, maze, 0, 0);

            totCandies = 0;
            fill(maze, startX, startY);
            int[][] xy = new int[totCandies][2];
            Node lol = bfs(maze, startX, startY);
            MIN = lol.steps;
            if (totCandies != 0) {
                xy[0][0] = lol.x;
                xy[0][1] = lol.y;
                maze = lol.maze.clone();
                for (int i = 0; i < totCandies; i++) {
                    lol = bfs(maze, xy[i][0], xy[i][1]);
                    MIN += lol.steps;
                    if (i < totCandies - 1) {
                        xy[i + 1][0] = lol.x;
                        xy[i + 1][1] = lol.y;
                    }
                    maze = lol.maze.clone();

                }
                System.out.println(totCandies + " " + MIN);
            } else {
                System.out.println(0 + " " + 0);
            }
            //System.out.println(candy + " " + lol);
            //dfs(maze, startX, startY, 0);
            //try {
            //   System.out.println(candy + " " + mini[candy - 1]);
            //} catch (Exception e) {
            //   System.out.println(0 + " " + 0);
            //}
        }
    }

    public static void fill(char[][] maze, int x, int y) {
        if (x < 0 || x > n1 - 1 || y < 0 || y > n1 - 1) {
            return;
        }
        if (maze[x][y] == '#') {
            return;
        }
        if (maze[x][y] == '*') {
            totCandies++;
        }
        if (maze[x][y] >= 'a' && maze[x][y] <= 'f') {
            if (totCandies < maze[x][y] - 'a' + 1) {
                return;
            }
        }
        maze[x][y] = '#';
        fill(maze, x + 1, y);
        fill(maze, x - 1, y);
        fill(maze, x, y + 1);
        fill(maze, x, y - 1);
    }
    //need to tweak

    public static Node bfs(char[][] maze, int xStart, int yStart) {
        Queue<Node> queue = new LinkedList<Node>();
        Node startNode = new Node(maze, xStart, yStart, 0);
        queue.add(startNode);
        while (queue.peek() != null) {
            Node array = queue.remove();
            int x = array.x;
            int y = array.y;;

            if (x > n1 - 1 || y > n1 - 1 || x < 0 || y < 0) {
                continue;
            }
            if (maze[x][y] == '#') {
                continue;
            }

            if (maze[x][y] == '*') {
                //MIN += array.steps;
                maze[x][y] = '.';
                return array;
            }
//            if (candy > cCount) {
//                candy = cCount;
//                return array;
//            }
//            if (maze[x][y] >= 'a' && maze[x][y] <= 'f') {
//                // System.out.println(maze[x][y]-'a'+" "+candy);
//                if (candy < maze[x][y] - 'a' + 1) {
//                    return array;
//                }
//            }
            int newPoints[][] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            for (int i = 0; i < 4; ++i) {
                Node node = new Node(maze, x + newPoints[i][0], y + newPoints[i][1], array.steps + 1);
                queue.add(node);
            }

            //maze[x][y] = '#';
        }
        Node newl = new Node(maze, 0, 0, 0);
        return newl;
    }
}

class Node {

    char[][] maze;
    int x;
    int y;
    int steps;

    public Node(char[][] maze, int x, int y, int steps) {
        this.y = y;
        this.x = x;
        this.steps = steps;
        this.maze = maze.clone();

    }
}
Author:  Tony [ Thu Dec 27, 2012 1:30 pm ]
Post subject:  RE:Help question
This is known as a Greedy Algorithm. It will probably work in most of the cases. An exception would be something like:
Quote:

*.B***

Where the optimal path involves going for the candy on the left first.
Author:  Panphobia [ Thu Dec 27, 2012 6:24 pm ]
Post subject:  RE:Help question
So I solved the problem partly with the greedy algorithm but I would like to know how to solve it by putting the number of candies in a queue and keep track of it that way, kinda lost with that

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy