在迷宮中使用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 
    } 

你在做的最後一項任務是讓每一個方格都進入牆壁。如果你能夠在沒有回溯的情況下穿過迷宮，這將是正確的方法，但事實並非如此。相反，你想要做的是確保你不會退縮，直到你拿起一塊新的糖果。所以，嘗試這樣的代替：

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

這樣，一旦你拿起一塊新的糖果廣場將再次可用。

但是，這裏仍然存在問題。想想BFS將如何在此地圖上的工作：

3 
... 
*B* 
... 

如果[0,0]是左上圖塊，那麼你的BFS算法將參觀瓷磚順序如下：[1,2]，[2 ，1]，[0,1]，[1,0]。那有什麼問題？比利正在他所有的鄰居廣場之間跳躍！你真正想要他做的是每次他拿到一塊新糖時重新啓動BFS。我會讓你知道如何做到這一點。

編輯

這裏是要遵循的基本算法：

1. 開始在start位置。
2. 使用BFS搜索最近的一塊糖果。在BFS找到的第一塊糖果是最近的（或者最近並列的）！
3. 找到一塊糖之後，你需要找到下一個最接近一塊你當前位置，因此可以看作是另一個BFS新start您的當前位置。

Answer 2

我剛剛完成解決它自己的方式，將「貪婪」這裏的方法是代碼

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

public class HalloweenCandy { 

static int n, candy; 
static int minsteps, maxcandy; 
static int totCandies = 0; 
static boolean[][] is; 

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]; 
     is = new boolean[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; 
     int tot = 0; 
     int y = 0, x = 0; 
     x = xStart; 
     y = yStart; 
     for (int j = 0; j < n; ++j) { 
      for (int i = 0; i < n; ++i) { 
       is[i][j] = false; 
      } 
     } 
     while (true) { 
      char[][] grid = new char[n][n]; 
      for (int j = 0; j < n; ++j) { 
       for (int i = 0; i < n; ++i) { 
        grid[i][j] = maze[i][j]; 
       } 
      } 
      int lol[] = BFS(grid, x, y); 
      if (lol[0] == -1) { 
       break; 
      } 
      y = lol[2]; 
      x = lol[1]; 
      tot += lol[0]; 
     } 
     System.out.println(candy + " " + tot); 
    } 
} 

public static int[] 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] == '*' && !is[x][y]) { 
      is[x][y] = true; 
      candy++; 
      int sta[] = {array[2], x, y}; 
      return sta; 

     } 
     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] = '#'; 
    } 
    int sta[] = {-1}; 
    return sta; 
} 
} 

我想現在弄清楚如何解決它的動態的方式，解決我只給了適用於某些情況，但不是全部。