LeetCode1293. グリッド内の最短パス(BFS,Java,python)
19278 ワード
1.質問
m*nのグリッドを1つあげます.各セルは0(空)ではなく1(障害物)です.各ステップで、空白のセルを上、下、左、右に移動できます.
最大k個の障害物を除去できる場合は、左上隅(0,0)から右下隅(m-1,n-1)までの最短パスを見つけ、パスを通過するために必要なステップ数を返します.このようなパスが見つからない場合は、-1を返します.
例1:
入力:
出力:6説明:障害を解消しない最短パスは10です.位置(3,2)の障害を取り除いた後,最短経路は6であった.この経路は(0,0)->(0,1)->(0,2)->(1,2)->(2,2)->(3,2)->(4,2)である.
例2:
入力:
出力:-1説明:このような経路を見つけるには、少なくとも2つの障害を除去する必要があります.
ヒント:
力ボタン(LeetCode)
2.解答
インプリメンテーション:BFSを使用して遍歴し、記録経路の長さと障害を塗りつぶすノードクラスの数を定義します.注目すべきは,BFSによる探索の過程で,障害の存在により既に遍歴しているノードに戻る場合があり,このとき新しいルートが通る障害が少ない限り,そのノードを更新することである.また、ヒントには、始点と終点が0であることが示されています.初期化の際に起点が1の場合を考慮する必要はありません.
JAva解答:
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;
}
}