我一直在尝试通过广度优先搜索来解决这个问题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]='#';
}
}
}