Hope Everyone Is Happy

[Hard] 1293. Shortest Path in a Grid with Obstacles Elimination (Java) 본문

※ 릿코드 ( LeetCode )/[Java] 문제 풀이 ( Solve the problems)

[Hard] 1293. Shortest Path in a Grid with Obstacles Elimination (Java)

J 크 2023. 12. 17. 15:26
728x90
반응형

https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/description/

 

Shortest Path in a Grid with Obstacles Elimination - LeetCode

Can you solve this real interview question? Shortest Path in a Grid with Obstacles Elimination - You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell

leetcode.com

Very hard..?

※  Question Summary

▶ There is m x n Integer array grid where each value has 0(empty) or 1(obstacle)

▶ You can move up, down, left, right from and to an empty cell in one step

▶ You can eliminate at most k obstacles

▶ Return the minimum number of steps to walk from the (0,0) to (m-1, n-1)

▶ if it's not possible to find such walk return -1

◈ Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 40
  • 1 <= k <= m * n
  • grid[i][j] is either 0 or 1.
  • grid[0][0] == grid[m - 1][n - 1] == 0

◈ Input - 1

grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1

◈ Output - 1

6

◈ Input - 2

grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1

◈ Output - 2

-1

 ◎  Solution 1 ( failed - time limit exceed )

▶ Create the class 'Point' which has the row and the col and the count of steps

▶ Initialize the result as '-1' to return -1 if there is no way to get last point 

▶ Create the function perm to check every case for eliminating obstacles

▶ Create the 2d array 'visit' to check if it's visited

▶ do the BFS for searching the way to get last point

 

◈ Last Executed Input 

[[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]
k=5
class Point {
    int m_nRow;
    int m_nCol;
    int m_nCount;

    Point(int nRow, int nCol, int nCount) {
        m_nRow = nRow;
        m_nCol = nCol;
        m_nCount = nCount;
    }
}

class Solution {
    int[] narrStacks;
    int[][] narrGrid;
    boolean[] barrStacks;
    ArrayList<Point> listObstacles;
    int nSteps;
    int K;
    public int shortestPath(int[][] grid, int k) {
        nSteps = Integer.MAX_VALUE;
        listObstacles = new ArrayList<>();
        // find the obstacles and copy the array
        narrGrid = new int[grid.length][grid[0].length];
        for(int i = 0 ; i < grid.length; i++) {
            for(int j = 0 ; j < grid[i].length; j++) {
                if(grid[i][j] == 1)
                    listObstacles.add(new Point(i, j, 0));
                narrGrid[i][j] = grid[i][j];
            }
        }
        K = 0;
        while(K <= k) {
            narrStacks = new int[K];
            barrStacks = new boolean[listObstacles.size()];
            
            perm(0);
            K++;
        }

        if(nSteps == Integer.MAX_VALUE)
            return -1;
        
        return nSteps;
    }

    public void perm(int nIndex) {
        if(nIndex == K){
            // eliminate K obstacles
            for(int i = 0; i < K; i++) {
                int nRow = listObstacles.get(narrStacks[i]).m_nRow;
                int nCol = listObstacles.get(narrStacks[i]).m_nCol;

                narrGrid[nRow][nCol] = 0;
            }

            BFS();

            // repair K obstacles since it's checked
            for(int i = 0; i < K; i++) {
                int nRow = listObstacles.get(narrStacks[i]).m_nRow;
                int nCol = listObstacles.get(narrStacks[i]).m_nCol;

                narrGrid[nRow][nCol] = 1;
            }

            return;
        }

        //
        for(int i = 0; i < listObstacles.size(); i++) {
            // ex) 0,1 == 1,0 so i don't have to search twice
            if(nIndex > 0 && narrStacks[nIndex-1] > i)
                continue;

            if(!barrStacks[i]) {
                narrStacks[nIndex] = i;
                barrStacks[i] = true;
                perm(nIndex+1);
                barrStacks[i] = false;
            }
        }
    }

    public void BFS() {
        // Search Dircetion
        int[] dr = {0, 0, 1, -1};
        int[] dc = {1, -1, 0, 0};
        boolean[][] barrVisit = new boolean[narrGrid.length][narrGrid[0].length];

        Queue<Point> BFS = new LinkedList<>();
        BFS.add(new Point(0,0,0));
        while(!BFS.isEmpty()) {
            Point p = BFS.poll();

            if(barrVisit[p.m_nRow][p.m_nCol])
                continue;

            if(p.m_nRow == narrGrid.length-1 && p.m_nCol == narrGrid[0].length -1){
                if(nSteps > p.m_nCount)
                    nSteps = p.m_nCount;
                return;
            }
            
            barrVisit[p.m_nRow][p.m_nCol] = true;

            for(int i = 0; i < dr.length; i++) {
                int nRow = p.m_nRow + dr[i];
                int nCol = p.m_nCol + dc[i];

                if(nRow < 0 || nCol < 0 || nRow >= narrGrid.length || nCol >= narrGrid[0].length)
                    continue;
                
                if(barrVisit[nRow][nCol] || narrGrid[nRow][nCol] == 1)
                    continue;

                BFS.add(new Point(nRow, nCol, p.m_nCount +1));
            }
        }
    }
}

 ◎  Solution 2 ( Accepted )

▶ Create the class 'Point' which has the row and the col and the count of steps, count of elimination

▶ Initialize the result as '-1' to return -1 if there is no way to get last point 

▶ Delete the function perm

▶ Create the 3d array 'visit' to check if it's visited with the row,col and the count of eliminate

    ( since it needs to be checked in every situation when eliminating obstacles )

▶ do the BFS for searching the way to get last point

▶ Return the count of steps when the first time get the point(m-1, n-1) since it means the shortest way

class Point {
    int m_nRow;
    int m_nCol;
    int m_nSteps;
    int m_nEliminate;

    Point(int nRow, int nCol, int nSteps, int nEliminate) {
        m_nRow = nRow;
        m_nCol = nCol;
        m_nSteps = nSteps;
        m_nEliminate = nEliminate;
    }
}

class Solution {
    int[][] narrGrid;
    int nSteps;
    int K;
    public int shortestPath(int[][] grid, int k) {
        nSteps = Integer.MAX_VALUE;
        //  copy the array
        narrGrid = new int[grid.length][grid[0].length];
        for(int i = 0 ; i < grid.length; i++) {
            for(int j = 0 ; j < grid[i].length; j++) {
                narrGrid[i][j] = grid[i][j];
            }
        }

        K = k;

        BFS();

        if(nSteps == Integer.MAX_VALUE)
            return -1;
        
        return nSteps;
    }

    public void BFS() {
        // Search Dircetion
        int[] dr = {0, 0, 1, -1};
        int[] dc = {1, -1, 0, 0};
        boolean[][][] barrVisit = new boolean[narrGrid.length][narrGrid[0].length][K+1];

        Queue<Point> BFS = new LinkedList<>();
        BFS.add(new Point(0,0,0,0));
        barrVisit[0][0][0] = true;
        while(!BFS.isEmpty()) {
            Point p = BFS.poll();

            if(p.m_nRow == narrGrid.length-1 && p.m_nCol == narrGrid[0].length -1){
                if(nSteps > p.m_nSteps)
                    nSteps = p.m_nSteps;
                return;
            }

            for(int i = 0; i < dr.length; i++) {
                int nRow = p.m_nRow + dr[i];
                int nCol = p.m_nCol + dc[i];

                if(nRow < 0 || nCol < 0 || nRow >= narrGrid.length || nCol >= narrGrid[0].length)
                    continue;
                
                int eliminate = p.m_nEliminate + narrGrid[nRow][nCol];
                if (eliminate > K || barrVisit[nRow][nCol][eliminate])
                    continue;

                barrVisit[nRow][nCol][eliminate] = true;
                BFS.add(new Point(nRow, nCol, p.m_nSteps + 1, eliminate));
            }
        }
    }
}

I HOPE YOUR DAY GOES WELL :)

저작자표시 비영리 변경금지

'※ 릿코드 ( LeetCode ) > [Java] 문제 풀이 ( Solve the problems)' 카테고리의 다른 글

[Hard] 818. Race Car (Java)  (0) 2023.12.18
[Hard] 2534. Time Taken to Cross the Door(Java)  (2) 2023.12.15
[Hard] 489. Robot Room Cleaner (Java)  (0) 2023.12.11
[Medium] 419. Battleships in a Board (Java)  (3) 2023.12.05
[Medium] 366. Find Leaves of Binary Tree (Java)  (0) 2023.12.04
'※ 릿코드 ( LeetCode )/[Java] 문제 풀이 ( Solve the problems)' Related Articles more