英文:
Leetcode Shortest Path in a Grid with Obstacles Elimination
问题
以下是翻译好的内容：
我在使用更大输入的网格大小时遇到了超时错误（TLE错误）。我应该如何改进以解决这个问题？
我在这里使用了回溯法。
给定一个 m * n 的网格，每个单元格可以是 0（空）或 1（障碍物）。在一步中，你可以从一个空单元格向上、向下、向左或向右移动，也可以移动到一个空单元格。
返回从左上角（0, 0）走到右下角（m-1, n-1）的最小步数，假设你最多可以消除 k 个障碍物。如果无法找到这样的路径，返回 -1。
class Solution {
int min = Integer.MAX_VALUE;
public int shortestPath(int[][] grid, int k) {
helper(grid, 0, 0, 0, 0, k);
return min == Integer.MAX_VALUE ? -1 : min;
}
void helper(int grid[][], int x, int y, int step, int obstacles, int k) {
if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || obstacles > k || grid[x][y] > 1) {
return;
}
if (x == grid.length - 1 && y == grid[0].length - 1) {
min = Math.min(min, step);
return;
}
if (grid[x][y] == 1) obstacles++;
int temp = grid[x][y];
grid[x][y] = 2;
helper(grid, x + 1, y, step + 1, obstacles, k);
helper(grid, x, y + 1, step + 1, obstacles, k);
helper(grid, x - 1, y, step + 1, obstacles, k);
helper(grid, x, y - 1, step + 1, obstacles, k);
grid[x][y] = temp;
}
}
有人能提供帮助吗？
英文:
I am getting TLE error for bigger input grid size. How can I improve to resolve it?
I am using backtracking here.
Given a m * n grid, where each cell is either 0 (empty) or 1 (obstacle). In one step, you can move up, down, left or right from and to an empty cell.
Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m-1, n-1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1. class Solution {
int min= Integer.MAX_VALUE;
public int shortestPath(int[][] grid, int k) {
helper(grid,0,0,0,0,k);
return min==Integer.MAX_VALUE?-1:min;
}
void helper(int grid[][],int x, int y, int step, int obstacles,int k){
if(x<0 || y<0 || x>=grid.length || y>=grid[0].length || obstacles>k || grid[x][y]>1){
return;
}
if(x==grid.length-1 && y==grid[0].length-1){
min = Math.min(min,step);
return;
}
if(grid[x][y]==1) obstacles++;
int temp = grid[x][y];
grid[x][y]=2;
helper(grid,x+1,y,step+1,obstacles,k);
helper(grid,x,y+1,step+1,obstacles,k);
helper(grid,x-1,y,step+1,obstacles,k);
helper(grid,x,y-1,step+1,obstacles,k);
grid[x][y]=temp;
}
}
Anyone Help?
答案1
得分: 1
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
static final int[][] directions = new int[][] {{0, 1}, {1, 0}, { -1, 0}, {0, -1}};
public static final int shortestPath(
final int[][] grid,
final int k
) {
final int rowLength = grid.length;
final int colLength = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
boolean[][][] visited = new boolean[rowLength][colLength][k + 1];
visited[0][0][0] = true;
queue.offer(new int[] {0, 0, 0});
int minSteps = 0;
while (!queue.isEmpty()) {
final int size = queue.size();
for (int i = 0; i < size; i++) {
final int[] info = queue.poll();
final int row = info[0];
final int col = info[1];
final int currObstacle = info[2];
if (row == rowLength - 1 && col == colLength - 1) {
return minSteps;
}
for (int[] direction : directions) {
final int nextRow = direction[0] + row;
final int nextCol = direction[1] + col;
int nextObstacle = currObstacle;
if (nextRow > -1 && nextRow < rowLength && nextCol > -1 && nextCol < colLength) {
if (grid[nextRow][nextCol] == 1) {
nextObstacle++;
}
if (nextObstacle <= k && !visited[nextRow][nextCol][nextObstacle]) {
visited[nextRow][nextCol][nextObstacle] = true;
queue.offer(new int[] {nextRow, nextCol, nextObstacle});
}
}
}
}
minSteps++;
}
return -1;
}
}
英文:
Looks pretty good so far!
- We'd probably want to check for
visitednodes.
This'd pass using a Queue and LinkedList:
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
static final int[][] directions = new int[][] {{0, 1}, {1, 0}, { -1, 0}, {0, -1}};
public static final int shortestPath(
final int[][] grid,
final int k
) {
final int rowLength = grid.length;
final int colLength = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
boolean[][][] visited = new boolean[rowLength][colLength][k + 1];
visited[0][0][0] = true;
queue.offer(new int[] {0, 0, 0});
int minSteps = 0;
while (!queue.isEmpty()) {
final int size = queue.size();
for (int i = 0; i < size; i++) {
final int[] info = queue.poll();
final int row = info[0];
final int col = info[1];
final int currObstacble = info[2];
if (row == rowLength - 1 && col == colLength - 1) {
return minSteps;
}
for (int[] direction : directions) {
final int nextRow = direction[0] + row;
final int nextCol = direction[1] + col;
int nextObstacle = currObstacble;
if (nextRow > -1 && nextRow < rowLength && nextCol > -1 && nextCol < colLength) {
if (grid[nextRow][nextCol] == 1) {
nextObstacle++;
}
if (nextObstacle <= k && !visited[nextRow][nextCol][nextObstacle]) {
visited[nextRow][nextCol][nextObstacle] = true;
queue.offer(new int[] {nextRow, nextCol, nextObstacle});
}
}
}
}
minSteps++;
}
return -1;
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论