迷宫中的改变大小

Question

在采访中有人问我，你给了一个填满“1”和“0”的矩阵，“1”表示你可以使用单元，“0”表示单元是您可以沿左右，上，下四个方向移动。每当您向上或向下移动时，您都会花费1美元。向左或向右移动不会增加成本。因此，您必须编写一个代码来检查是否可以从（0,0）开始到达目标索引（x，y）。如果是，则打印最低成本，如果不是，则打印“-1”。

我无法计算成本。 这里是我的代码

public class Test { 

    /** 
    * @param args the command line arguments 
    */ 
    static int dest_x = 0; 
    static int dest_y = 0; 
    static int cost = 0; 
    static int m = 0; 
    static int n = 0; 

    public static void main(String[] args) { 
     // TODO code application logic here 
     Scanner in = new Scanner(System.in); 
     Test rat = new Test(); 
     int maze[][] = { 
       {1, 1, 1, 1}, 
       {1, 1, 1, 0}, 
       {1, 1, 1, 1}, 
       {0, 0, 1, 1} 
     }; 
     dest_x = in.nextInt(); 
     dest_y = in.nextInt(); 
     m = in.nextInt(); 
     n = in.nextInt(); 
     if (rat.solveMaze(maze)) 
      System.out.println("YES"); 

     else { 
      System.out.println("NO"); 
     } 
     System.out.println("cost = " + cost); 
    } 

    boolean isSafe(int maze[][], int x, int y) { 
     // if (x,y outside maze) return false 
     return (x >= 0 && x < m && y >= 0 && 
       y < n && maze[x][y] == 1); 
    } 

    boolean solveMaze(int maze[][]) { 
     int sol[][] = {{0, 0, 0, 0}, 
       {0, 0, 0, 0}, 
       {0, 0, 0, 0}, 
       {0, 0, 0, 0} 
     }; 

     if (!solveMazeUtil(maze, 0, 0, sol)) { 
      return false; 
     } 
     return true; 
    } 

    boolean solveMazeUtil(int maze[][], int x, int y, int sol[][]) { 
     // if (x,y is goal) return true 
     if (x <= dest_x || y <= dest_y) 
      if (x == dest_x && y == dest_y) { 
       sol[x][y] = 1; 
       return true; 
      } else if (sol[x][y] == 1) { 
       return false; 
      } 

      // Check if maze[x][y] is valid 
      else if (isSafe(maze, x, y)) { 
       // mark x,y as part of solution path 
       sol[x][y] = 1; 

       // Move forward in x direction 
       if (solveMazeUtil(maze, x + 1, y, sol)) { 
        //System.out.println("here at x+1 x = " + x + " y = " + y); 
        return true; 
       } 

       // Move down in y direction 
       if (solveMazeUtil(maze, x, y + 1, sol)) { 
        //System.out.println("here at y+1 x = " + x + " y = " + y); 
        cost++; 
        return true; 
       } 
       cost--; 
       if (solveMazeUtil(maze, x - 1, y, sol)) { 
        // System.out.println("here at x-1 x = " + x + " y = " + y); 
        return true; 
       } 
       if (solveMazeUtil(maze, x, y - 1, sol)) { 
        //System.out.println("here at y-1 x = " + x + " y = " + y); 
        cost++; 
        return true; 
       } 
       cost--; 
       /* If no solution then 
        BACKTRACK: unmark x,y as part of solution 
        path */ 
       sol[x][y] = 0; 
       return false; 
      } 
     return false; 
    } 
} 

Answer 1

打开迷宫成向图解决最短路径问题，这是由"1"标记是节点

1. 细胞（标记为"0"应忽略）
2. 如果我们可以从一个单元格（节点）移动到另一个单元格，请将它们与一个定向的边缘;把的成本（0或1）的边缘（请注意，我们有一个多图：两个节点可以连接两个不同的边缘）。
3. 最后，在Dijkstra's algorithm的帮助下，在所需节点之间找到最短路径（即最小成本）。