求一个矩阵从左上角遍历到右下角需要的步数

Question

矩阵 A 有 6 行 4 列。其中 '#' = blocked path 和 '.' = allowed path..

A = [[. . . #], 
     [# . # #], 
     [# . # .], 
     [# . . .], 
     [# . . .],
     [# . . .]
    ]

如何找到从左上到下到达所需的步数 left.I 我可以从左上到右下遍历矩阵但无法找到 steps(which is 8 here).。但是下面的代码我得到的答案是 12 这是错误的

我的代码如下：

private static int numSteps(char[][] A) {
        
        int row = A.length;
        
        int col = A[0].length;
        
        // directions array for row and column
        // for north, south, east , west
        int r[] = {-1, 1, 0, 0};
        int c[] = {0, 0, 1, -1};
        
        int steps = 0;
        
        LinkedList<String> queuePos = new LinkedList<String>();
        
        queuePos.add("0,0");
        
        boolean[][] visited = new boolean[row][col];
        
        while(!queuePos.isEmpty()) {
            
                String pos = queuePos.poll();
                int rowPos = Integer.parseInt(pos.split(",")[0]);
                int colPos = Integer.parseInt(pos.split(",")[1]);
                
                if(rowPos >= row - 1 && colPos>= col -1) {
                    
                    return steps;
                    
                }
                
                // looping for the four directions for surrounding nodes/neighbours
                for(int i=0; i<r.length; i++) {
                    
                    int newRow = rowPos + r[i];
                    
                    int newCol = colPos + c[i];
                    
                    if(newRow < 0 || newCol < 0 || newRow >= row || newCol >= col || A[newRow][newCol] == '#' || visited[newRow][newCol]) {
                        
                        continue;
                        
                    }
                    
                    visited[newRow][newCol] = true;
                    
                    queuePos.add(newRow + "," + newCol);
                    
                    if(newRow == row - 1 && newCol == col -1) {
                        
                        return steps;
                        
                    }
                    
            }
            
            
            steps+=1;
            
        }
        
        return steps;
        
    }

我不知道应该在哪里将 "steps" 变量增加 1..有人可以在这里提出更正建议吗？

Answer 1

由于您使用的是 BFS，因此在每一步中您都应该使用队列中的所有元素，因此您在 while 循环中忘记了以下代码行：

while(!queuePos.isEmpty()) {
    int size = queuePos.size();
    for (int idx = 0; idx < size; idx++) {
    ...
    }
    steps+=1;
}

此外，这些代码行不是必需的，当你从队列中获得一个位置时检查它们(queue.poll())

if(newRow == row - 1 && newCol == col -1) {
    return steps;
}

所以，稍微修改的版本是：

    private static int numSteps(char[][] A) {

        int row = A.length;

        int col = A[0].length;

        // directions array for row and column
        // for north, south, east , west
        int r[] = {-1, 1, 0, 0};
        int c[] = {0, 0, 1, -1};

        int steps = 0;

        LinkedList<String> queuePos = new LinkedList<String>();

        queuePos.add("0,0");

        boolean[][] visited = new boolean[row][col];

        while(!queuePos.isEmpty()) {

            int size = queuePos.size();
            for (int idx = 0; idx < size; idx++) {
                String pos = queuePos.poll();
                int rowPos = Integer.parseInt(pos.split(",")[0]);
                int colPos = Integer.parseInt(pos.split(",")[1]);

                if(rowPos >= row - 1 && colPos>= col -1) {

                    return steps;

                }

                // looping for the four directions for surrounding nodes/neighbours
                for(int i=0; i<r.length; i++) {

                    int newRow = rowPos + r[i];

                    int newCol = colPos + c[i];

                    if(newRow < 0 || newCol < 0 || newRow >= row || newCol >= col || A[newRow][newCol] == '#' || visited[newRow][newCol]) {

                        continue;

                    }

                    visited[newRow][newCol] = true;

                    queuePos.add(newRow + "," + newCol);
                }
            }


            steps+=1;

        }

        return steps;

    }

求一个矩阵从左上角遍历到右下角需要的步数

Find Number of steps needed to traverse from one top left to bottom right in a matrix

java

depth-first-search

breadth-first-search

path-finding