我一直试图用广度优先搜索来解决这个问题http://dwite.ca/questions/haunted_house.html,但是我无法得到所有的测试用例都是正确的,我认为问题在于,它只会计算到最后的直接最短路径,将计算任何糖果打开,但它不会指望通过这里的糖果的最短路径是代码在迷宫中使用BFS?
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
如此贪婪的方法?或者当你得到糖果时你的意思是继续bfs循环吗? – ultrainstinct 2013-03-16 01:37:56
@Panphobia - 查看我上面的修改。 – DaoWen 2013-03-16 01:55:24
类似[Star,Dot,B,Star,Star,Star]不会起作用,因为我不能使用星号和点,因为它阻止了它的一部分。因为那么最佳的解决方案是从最左边的星球开始 – ultrainstinct 2013-03-16 02:03:59