java - 使用 BFS 构建迷宫？

Question

我一直在尝试解决这个问题http://dwite.ca/questions/haunted_house.html使用广度优先搜索，但我无法让所有测试用例都正确，我认为问题在于，它只会计算到末尾的直接最短路径，并且会计算任何打开的糖果，但不会计算穿过糖果的最短路径是代码

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

public class HalloweenCandy {

    static int n, candy;
    static int minsteps, maxcandy;
    static int totCandies=0;
    public static void main(String[] args) throws FileNotFoundException {
        Scanner s = new Scanner(new File("C:\\Users\\Daniel\\Desktop\\Java\\HalloweenCandy\\src\\halloweencandy\\DATA5.txt"));

        while (s.hasNext()) {
            n=Integer.parseInt(s.nextLine().trim());
            char[][]maze=new char[n][n];
            int xStart =0;
            int yStart =0;

            for(int y=0;y<n;++y){
                String text = s.nextLine().trim();
                for(int x=0;x<n;++x){

                    maze[x][y]=text.charAt(x);
                    if(maze[x][y]=='B'){
                        xStart=x;
                        yStart=y;
                    }
                }
            }
            candy=0;
            minsteps=0;
            BFS(maze,xStart,yStart);
            System.out.println(candy+" "+minsteps);
        }
    }
    public static void BFS(char[][]maze,int xStart,int yStart){
        Queue<int[]>queue=new LinkedList<int[]>();
        int start[]={xStart,yStart,0,0};
        queue.add(start);

        while(queue.peek()!=null){
            int[]array=queue.poll();
            int x=array[0];int y=array[1];

            if(x<0||y<0||y>n-1||x>n-1)continue;
            if(maze[x][y]=='#')continue;
            if(maze[x][y]=='*'){                 
                candy++;               
                minsteps=array[2];
                maze[x][y]='.';
            }
            if(maze[x][y]>='a'&&maze[x][y]<='f'){
                if(candy <maze[x][y]-'a'+1)continue;
            }
            int[][]points = {{0,1},{1,0},{-1,0},{0,-1}};
            for(int i=0;i<4;++i){
                int sta[]={x+points[i][0],y+points[i][1],array[2]+1};
                queue.add(sta);
            }
           maze[x][y]='#';
        }

    }
}

这是测试用例 http://dwite.ca/home/testcase/232.html

Answer 1

您正在写作，但您错过了一些重要的事情。

    while(queue.peek()!=null){
        int[]array=queue.poll();
        int x=array[0];int y=array[1];

        if(x<0||y<0||y>n-1||x>n-1)continue;
        if(maze[x][y]=='#')continue;
        if(maze[x][y]=='*'){                 
            candy++;               
            minsteps=array[2];
            maze[x][y]='.';
        }
        if(maze[x][y]>='a'&&maze[x][y]<='f'){
            if(candy <maze[x][y]-'a'+1)continue;
        }
        int[][]points = {{0,1},{1,0},{-1,0},{0,-1}};
        for(int i=0;i<4;++i){
            int sta[]={x+points[i][0],y+points[i][1],array[2]+1};
            queue.add(sta);
        }
       maze[x][y]='#'; // <== this part is wrong
    }

你在最后一个任务中所做的就是将你踩过的每一个方 block 变成一堵墙。如果您可以不走回头路地穿过迷宫，这将是正确的方法，但事实并非如此。相反，你要做的是确保在拿起一 block 新糖果之前不会原路返回。所以，尝试这样的事情:

maze[x][y]='a'+candy;

这样，一旦您拿起一 block 新糖果，该方 block 就可以再次使用。

但是，这里仍然存在一个问题。想想 BFS 在这张 map 上是如何工作的:

3
...
*B*
...

如果 [0,0] 是左上角的图 block ，那么您的 BFS 算法将按以下顺序访问图 block :[1,2]、[2,1]、[0,1]、[1,0 ]。这有什么问题吗？比利正在他所有相邻的方 block 之间跳跃!你真正希望他做的是每次他得到一 block 新糖果时重新启动 BFS。我将让您自行弄清楚如何完成该部分。

编辑

这是您要遵循的基本算法:

1. 从开始位置开始。
2. 使用 BFS 搜索最近的一 block 糖果。用 BFS 找到的第一 block 糖果是最近的(或并列最近的)!
3. 找到一 block 糖果后，您需要找到距离您当前位置最近的下一个糖果，因此请将您当前的位置视为新的开始 另一个 BFS。