# 1293. 网格中的最短路径(1293. Shortest path in Grid)-其他

## 1293. 网格中的最短路径(1293. Shortest path in Grid)

### 深度优先搜索 + 记忆化（错误）

dp数组存储的不一定是最优值

dp数组存储的不一定是最优值

``````import java.util.Arrays;

class Solution {

private static final int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

private int[][][] dp;

private int[][] grid;

private boolean[][] visited;

private int solve(int x, int y, int k) {
if (dp[x][y][k] == -1) {
if (grid[x][y] == 1 && k == 0) {
dp[x][y][k] = Integer.MAX_VALUE;
return Integer.MAX_VALUE;
}

if (x == grid.length - 1 && y == grid[0].length - 1) {
dp[x][y][k] = 0;
return 0;
}

if (grid[x][y] == 1) {
k--;
}

int ans = Integer.MAX_VALUE;
for (int i = 0; i < directions.length; ++i) {
int nx = x + directions[i][0];
int ny = y + directions[i][1];
if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && !visited[nx][ny]) {
visited[nx][ny] = true;
ans = Math.min(ans, solve(nx, ny, k));
visited[nx][ny] = false;
}
}
dp[x][y][k] = ans == Integer.MAX_VALUE ? ans : ans + 1;
}
return dp[x][y][k];
}

public int shortestPath(int[][] grid, int k) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
this.grid = grid;
this.visited = new boolean[grid.length][grid[0].length];
this.dp = new int[grid.length][grid[0].length][k + 1];
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid[0].length; ++j) {
Arrays.fill(dp[i][j], -1);
}
}
visited[0][0] = true;
int ans = solve(0, 0, k);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
}
``````

### 广度优先搜索

``````import java.util.Arrays;
import java.util.Queue;

class Solution {

private static final int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

public int shortestPath(int[][] grid, int k) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length, n = grid[0].length;
if (m == 1 && n == 1) {
return 0;
}
k = Math.min(m + n - 3, k);
boolean[][][] visited = new boolean[m][n][k + 1];
visited[0][0][k] = true;
queue.offer(new Info(0, 0, 0, k));
while (!queue.isEmpty()) {
Info node = queue.poll();
if (node.x == m - 1 && node.y == n - 1) {
return node.step;
}
for (int i = 0; i < directions.length; ++i) {
int nx = node.x + directions[i][0];
int ny = node.y + directions[i][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (grid[nx][ny] == 1) {
if (node.k > 0 && !visited[nx][ny][node.k - 1]) {
visited[nx][ny][node.k - 1] = true;
queue.offer(new Info(nx, ny, node.step + 1, node.k - 1));
}
} else {
if (!visited[nx][ny][node.k]) {
visited[nx][ny][node.k] = true;
queue.offer(new Info(nx, ny, node.step + 1, node.k));
}
}
}
}
}

return -1;
}

public static void main(String[] args) {
int[][] grid = {{0}};
int k = 2;
System.out.println(new Solution().shortestPath(grid, k));
}
}

class Info {
int x;
int y;
int step;
int k;

public Info(int x, int y, int step, int k) {
this.x = x;
this.y = y;
this.step = step;
this.k = k;
}
}
``````
————————

Give you a grid of ， m * n ， where each cell is either ， 0 (empty) or ， 1 (obstacle). At each step, you can move up, down, left and right in blank cells.

If you can remove up to K obstacles, find the shortest path from the upper left corner (0, 0) to the lower right corner (m-1, n-1) and return to the number of steps required to pass through the path. If no such path is found, – 1 is returned.

Source: leetcode

### Depth first search + memorization (error)

DP arrays do not necessarily store optimal values

DP arrays do not necessarily store optimal values

``````import java.util.Arrays;

class Solution {

private static final int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

private int[][][] dp;

private int[][] grid;

private boolean[][] visited;

private int solve(int x, int y, int k) {
if (dp[x][y][k] == -1) {
if (grid[x][y] == 1 && k == 0) {
dp[x][y][k] = Integer.MAX_VALUE;
return Integer.MAX_VALUE;
}

if (x == grid.length - 1 && y == grid[0].length - 1) {
dp[x][y][k] = 0;
return 0;
}

if (grid[x][y] == 1) {
k--;
}

int ans = Integer.MAX_VALUE;
for (int i = 0; i < directions.length; ++i) {
int nx = x + directions[i][0];
int ny = y + directions[i][1];
if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && !visited[nx][ny]) {
visited[nx][ny] = true;
ans = Math.min(ans, solve(nx, ny, k));
visited[nx][ny] = false;
}
}
dp[x][y][k] = ans == Integer.MAX_VALUE ? ans : ans + 1;
}
return dp[x][y][k];
}

public int shortestPath(int[][] grid, int k) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
this.grid = grid;
this.visited = new boolean[grid.length][grid[0].length];
this.dp = new int[grid.length][grid[0].length][k + 1];
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid[0].length; ++j) {
Arrays.fill(dp[i][j], -1);
}
}
visited[0][0] = true;
int ans = solve(0, 0, k);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
}
``````

``````import java.util.Arrays;
import java.util.Queue;

class Solution {

private static final int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

public int shortestPath(int[][] grid, int k) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length, n = grid[0].length;
if (m == 1 && n == 1) {
return 0;
}
k = Math.min(m + n - 3, k);
boolean[][][] visited = new boolean[m][n][k + 1];
visited[0][0][k] = true;
queue.offer(new Info(0, 0, 0, k));
while (!queue.isEmpty()) {
Info node = queue.poll();
if (node.x == m - 1 && node.y == n - 1) {
return node.step;
}
for (int i = 0; i < directions.length; ++i) {
int nx = node.x + directions[i][0];
int ny = node.y + directions[i][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (grid[nx][ny] == 1) {
if (node.k > 0 && !visited[nx][ny][node.k - 1]) {
visited[nx][ny][node.k - 1] = true;
queue.offer(new Info(nx, ny, node.step + 1, node.k - 1));
}
} else {
if (!visited[nx][ny][node.k]) {
visited[nx][ny][node.k] = true;
queue.offer(new Info(nx, ny, node.step + 1, node.k));
}
}
}
}
}

return -1;
}

public static void main(String[] args) {
int[][] grid = {{0}};
int k = 2;
System.out.println(new Solution().shortestPath(grid, k));
}
}

class Info {
int x;
int y;
int step;
int k;

public Info(int x, int y, int step, int k) {
this.x = x;
this.y = y;
this.step = step;
this.k = k;
}
}
``````