LeetCode1293. グリッド内の最短パス(BFS,Java,python)

19278 ワード

1.質問
m*nのグリッドを1つあげます.各セルは0(空)ではなく1(障害物)です.各ステップで、空白のセルを上、下、左、右に移動できます.
最大k個の障害物を除去できる場合は、左上隅(0,0)から右下隅(m-1,n-1)までの最短パスを見つけ、パスを通過するために必要なステップ数を返します.このようなパスが見つからない場合は、-1を返します.
例1:
入力:
grid = 
[[0,0,0],
 [1,1,0],
 [0,0,0],
 [0,1,1],
 [0,0,0]], 
k = 1

出力:6説明:障害を解消しない最短パスは10です.位置(3,2)の障害を取り除いた後,最短経路は6であった.この経路は(0,0)->(0,1)->(0,2)->(1,2)->(2,2)->(3,2)->(4,2)である.
例2:
入力:
grid = 
[[0,1,1],
 [1,1,1],
 [1,0,0]], 
k = 1

出力:-1説明:このような経路を見つけるには、少なくとも2つの障害を除去する必要があります.
ヒント:
grid.length == m
grid[0].length == n
1 <= m, n <= 40
1 <= k <= m*n
grid[i][j] == 0 or 1
grid[0][0] == grid[m-1][n-1] == 0

力ボタン(LeetCode)
2.解答
インプリメンテーション:BFSを使用して遍歴し、記録経路の長さと障害を塗りつぶすノードクラスの数を定義します.注目すべきは,BFSによる探索の過程で,障害の存在により既に遍歴しているノードに戻る場合があり,このとき新しいルートが通る障害が少ない限り,そのノードを更新することである.また、ヒントには、始点と終点が0であることが示されています.初期化の際に起点が1の場合を考慮する必要はありません.
JAva解答:

class Solution{
    class Node{
        int row;
        int col;
        int oneCount;
        int pathLen;
        Node (int row, int col, int oneCount, int pathLen){
            this.row = row;
            this.col = col;
            this.oneCount = oneCount;
            this.pathLen = pathLen;
        }
    }
    public int shortestPath(int[][] grid, int k){
        int m = grid.length;
        int n = grid[0].length;
        LinkedList<Node> queue = new LinkedList<>();
        Node rootNode = new Node(0,0,0,0);
        queue.add(rootNode);
        Node[][] visited = new Node[m][n];
        visited[0][0] = rootNode;
        int dx[] = new int[]{-1,1,0,0};
        int dy[] = new int[]{0,0,1,-1};
        
        while(!queue.isEmpty()){
            int count = queue.size();
            while(count-->0){
                Node tmp = queue.poll();
                int row = tmp.row;
                int col = tmp.col;
                int oneCount = tmp.oneCount;
                int pathLen = tmp.pathLen;
                if(row == m-1 && col == n-1 ){
                    return pathLen;
                }
                //four directions
                for(int i = 0;i < 4;i++){
                    int newRow = row + dx[i];
                    int newCol = col + dy[i];
                    if(newRow<0 || newRow>=m || newCol<0 || newCol>=n ){
                        continue;
                    }
                    int newOneCount = grid[newRow][newCol] == 1? oneCount+1:oneCount;
                    if(newOneCount > k){
                        continue;
                    }
                    Node newNode = new Node(newRow, newCol, newOneCount,pathLen+1);
                    if(visited[newRow][newCol] == null || newOneCount<visited[newRow][newCol].oneCount){
                        visited[newRow][newCol] = newNode;
                        queue.add(newNode);
                    }
                }
            }

        }
        return -1;
    }
}