# 1293. Shortest Path in a Grid with Obstacles Elimination ![](/files/VansadWSbvw4jD05GIoY) ![](/files/9Gc6kE2oLyEd4KvIWRHF) add one more dimension in visited \[x]\[y]k+1]: 記錄在某座標, 第三維紀錄 使用的消除次數 0\~k （boolean so ``` 然後分有障礙的座標和沒障礙的座標去處理 if (grid[x][y] == 1) else ``` 再遇到有障礙的座標時, 這樣代表用完了 ``` if (k == obs || visited[x][y][k+1]) k == obs, 代表 消除次數用到 k 次了, 不能再用 visited[x][y][k+1] 代表在這座標上 消除次數的狀態（true, 代表 k次消除次數在這座標用了 in next queue poll, we can get from previous xy 座標和 用了幾次消除次數（k) ``` T: O(mnk) , mn is the be the number of cells in the grid, and K be the quota to eliminate obstacles. S: O(mnk) ```java class Solution { private int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}}; public int shortestPath(int[][] grid, int obs) { int m = grid.length; int n = grid[0].length; // 注意 visited 狀態可以這樣寫, 多一個 "使用的消除障礙數" boolean visited[][][] = new boolean[m][n][obs+1]; // obs: 0~obs => obs+1 Queue queue = new ArrayDeque<>(); queue.offer(new int[]{0,0,0}); visited[0][0][0] = true; int steps = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int[] curr = queue.poll(); int currX = curr[0]; int currY = curr[1]; int k = curr[2]; // 寫在外面的優點是, 當只有一個 data 時, 這邊是可以返回的, 寫在內層無法, 要特別處理 if (currX == m - 1 && currY == n - 1) { return steps; } for (int dir[] : dirs) { int x = currX + dir[0]; int y = currY + dir[1]; if (!isInArea(grid, x, y)) { continue; } if (grid[x][y] == 1) { // 如果是障礙, 需要用消除障礙, 才能繼續加到 queue bfs if (k == obs || visited[x][y][k+1]) { // k == obs, 已經用完消除障礙的 continue; } queue.offer(new int[]{x, y, k+1}); // 消除障礙數目+1 visited[x][y][k+1] = true; } else { // 非障礙, 正常處理 if (visited[x][y][k]) { continue; } queue.offer(new int[]{x, y, k}); visited[x][y][k] = true; } } } steps++; } return -1; } private boolean isInArea(int[][] grid, int i, int j) { return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length; } } /* T: O(mnk) S: O(mnk) define visited[i][j][k] if (next 4 dir + (i,j)) == 1) if k == K continue; visited[new i][new j][k+1] if (next 4 dir + (i,j)) == 0) visited[new i][new j][k] */ ``` ## simpler version ```java class Solution { private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; public int shortestPath(int[][] grid, int k) { int m = grid.length; int n = grid[0].length; boolean[][][] visited = new boolean[m][n][k+1]; Queue queue = new LinkedList<>(); queue.offer(new int[]{0, 0, 0}); visited[0][0][0] = true; int steps = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int[] cur = queue.poll(); int curX = cur[0]; int curY = cur[1]; int curObs = cur[2]; if (curX == m - 1 && curY == n - 1) { return steps; } for (int[] dir : DIRS) { int x = dir[0] + curX; int y = dir[1] + curY; // alert!! this curObs must assign to a new variable(obs), // or it will be wrong!!! int obs = curObs; if (!isValid(grid, x, y)) { continue; } if (grid[x][y] == 1) { obs++; } if (obs > k || visited[x][y][obs]) { continue; } queue.offer(new int[] {x, y, obs}); visited[x][y][obs] = true; } } steps++; } return -1; } private boolean isValid(int[][] grid, int x, int y) { int m = grid.length; int n = grid[0].length; return x >= 0 && x < m && y >= 0 && y < n; } } ``` ## print with path ```java class Solution { private static final int[][] DIRS = {{1,0}, {-1,0}, {0,1}, {0,-1}}; private static final String[] DIRSTR = {"d", "u", "r", "l"}; // row col base class Data { int x; int y; int obs; String path; Data (int x, int y, int obs, String path) { this.x = x; this.y = y; this.obs = obs; this.path = path; } } public int shortestPath(int[][] grid, int k) { int m = grid.length; int n = grid[0].length; boolean[][][] visited = new boolean[m][n][k+1]; // k+1 ! Queue queue = new LinkedList<>(); queue.offer(new Data(0 , 0, 0, "")); visited[0][0][0] = true; int steps = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int q = 0; q < size; q++) { Data cur = queue.poll(); int curX = cur.x; int curY = cur.y; int curObs = cur.obs; String curPath = cur.path; if (curX == m - 1 && curY == n - 1) { System.out.println("final path:" + curPath); return steps; } for (int i = 0; i < 4; i++) { int x = curX + DIRS[i][0]; int y = curY + DIRS[i][1]; int obs = curObs; String path = curPath + DIRSTR[i]; if (!isValid(m, n, x, y)) { continue; } if (grid[x][y] == 1) { obs++; } if (obs > k || visited[x][y][obs]) { continue; } queue.offer(new Data(x , y, obs, path)); visited[x][y][obs] = true; } } steps++; } return -1; } private boolean isValid(int m, int n, int x, int y) { return x >= 0 && x < m && y >= 0 && y < n; } } /* weight is 1 BFS you can eliminate at most k obstacles => use one more dim to record eliminatation times <= k Queue => int[x][y][k] start from 0,0 end to m-1, n-1 T: O(mnk) S: O(mnk) */ ``` ![](/files/ukuSwt6cBmD11lEmm3mY) ![](/files/VxYAfbj2PmorPBXqqpkJ) ## shorter version ```java class Solution { private static final int[][] DIRS = {{0,1}, {1,0}, {0,-1}, {-1,0}}; public int shortestPath(int[][] grid, int k) { int m = grid.length; int n = grid[0].length; boolean[][][] visited = new boolean[m][n][k+1]; // 0~k obs Queue queue = new LinkedList<>(); queue.offer(new int[]{0 , 0, 0}); visited[0][0][0] = true; int steps = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int[] cur = queue.poll(); if (cur[0] == m-1 && cur[1] == n - 1) { return steps; } for (int[] dir : DIRS) { int x = cur[0] + dir[0]; int y = cur[1] + dir[1]; int toolUsedCount = cur[2]; if (!inArea(grid, x, y)) { continue; } if (grid[x][y] == 1) { // if is obstacle, use tool to eliminate toolUsedCount++; } if (toolUsedCount > k || visited[x][y][toolUsedCount]) { continue; } queue.offer(new int[]{x, y, toolUsedCount}); visited[x][y][toolUsedCount] = true; } } steps++; } return -1; } private boolean inArea(int[][] grid, int x, int y) { return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length; } } /* 010 000 010 */ ``` ### new version ````java ```java class Solution { private int[][] DIRECTIONS = {{0,1}, {1,0}, {0,-1}, {-1,0}}; class Step { int x; int y; int level; int removeCount; Step(int x, int y, int level, int removeCount) { this.x = x; this.y = y; this.level = level; this.removeCount = removeCount; } } public int shortestPath(int[][] grid, int k) { int m = grid.length; int n = grid[0].length; Queue queue = new LinkedList<>(); queue.offer(new Step(0, 0, 0, 0)); boolean[][][] visited = new boolean[m][n][k+1]; while (!queue.isEmpty()) { Step cur = queue.poll(); if (!inArea(grid, cur.x, cur.y) || visited[cur.x][cur.y][cur.removeCount]) { continue; } if (cur.x == m-1 && cur.y == n-1) { return cur.level; } visited[cur.x][cur.y][cur.removeCount] = true; for (int[] dir : DIRECTIONS) { int x = cur.x + dir[0]; int y = cur.y + dir[1]; int count = cur.removeCount; if (inArea(grid, x, y) && grid[x][y] == 1) { count++; } if (count > k) { continue; } queue.offer(new Step(x, y, cur.level+1, count)); } } return -1; } private boolean inArea(int[][] grid, int x, int y) { int m = grid.length; int n = grid[0].length; return x >= 0 && x < m && y >= 0 && y < n; } } ``` ```` ### More consistent way or ...still check count first... all good ````java ```java class Solution { private static final int[][] DIRECTIONS = {{1,0}, {0, 1}, {-1,0}, {0, -1}}; class Step { int x; int y; int level; int removedObstacles; Step(int x, int y, int level, int removedObstacles) { this.x = x; this.y = y; this.level = level; this.removedObstacles = removedObstacles; } } public int shortestPath(int[][] grid, int k) { int m = grid.length; int n = grid[0].length; Queue queue = new LinkedList<>(); queue.offer(new Step(0, 0, 0, 0)); boolean[][][] visited = new boolean[m][n][k+1]; while (!queue.isEmpty()) { Step cur = queue.poll(); // more consistent way if (!inArea(grid, cur.x, cur.y) || cur.removedObstacles > k || visited[cur.x][cur.y][cur.removedObstacles]) { continue; } visited[cur.x][cur.y][cur.removedObstacles] = true; if (cur.x == m - 1 && cur.y == n-1) { return cur.level; } for (int[] dir : DIRECTIONS) { int nextX = cur.x + dir[0]; int nextY = cur.y + dir[1]; int count = cur.removedObstacles; if (inArea(grid, nextX, nextY) && grid[nextX][nextY] == 1) { count++; } queue.offer(new Step(nextX, nextY, cur.level + 1, count)); } } return -1; } private boolean inArea(int[][] grid, int x, int y) { int m = grid.length; int n = grid[0].length; return x >= 0 && x < m && y >=0 && y < n; } } ``` ```` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/bfs/1293.-shortest-path-in-a-grid-with-obstacles-elimination.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.