🚀 2 Solutions for Shortest Path on Matrix: BFS 🌐, Dijkstra's Algorithm 🏃‍♂️, and DP 📊
\n\n# BFS Dijkstra\'s Solution Code\njava []\nclass Solution {\n    public boolean findSafeWalk(List<List<Integer>> grid, int health) {\n        int n = grid.si
\n\n# BFS Dijkstra\'s Solution Code\n```java []\nclass Solution {\n    public boolean findSafeWalk(List<List<Integer>> grid, int health) {\n        int n = grid.size();\n        int m = grid.get(0).size();\n        int dir[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };\n        PriorityQueue<Pair<Integer, int[]>> pq = new PriorityQueue<>(\n                (a, b) -> (Integer.compare(b.getKey(), a.getKey())));\n        pq.add(new Pair(health - grid.get(0).get(0), new int[] { 0, 0 }));\n        int[][] cost = new int[n][m];\n        for (int[] row : cost) {\n            Arrays.fill(row, Integer.MIN_VALUE);\n        }\n        while (!pq.isEmpty()) {\n            int hlt = pq.peek().getKey();\n            int curr[] = pq.peek().getValue();\n            pq.remove();\n            for (int d[] : dir) {\n                int i = curr[0] + d[0];\n                int j = curr[1] + d[1];\n\n                if (i < n && i >= 0 && j >= 0 && j < m && hlt - grid.get(i).get(j) > cost[i][j]\n                        && hlt - grid.get(i).get(j) > 0) {\n                    cost[i][j] = hlt - grid.get(i).get(j);\n                    pq.add(new Pair(cost[i][j], new int[] { i, j }));\n                }\n            }\n        }\n        return cost[n - 1][m - 1] >= 1;\n    }\n}\n```\n\n# Dynamic Programming Solution Code\n```\nclass Solution {\n    boolean[][] vis;\n    int[][][] dp;\n    boolean check(List<List<Integer>> grid, int row, int col, int hlt) {\n        int m = grid.size(); int n = grid.get(0).size();\n        if (row >= m || col >= n || row<0 || col<0 || hlt<=0 || vis[row][col]) return false;\n        if (row==m-1 && col==n-1) {\n            return hlt>grid.get(row).get(col);\n        }\n        if (dp[row][col][hlt]!=-1) return dp[row][col][hlt]==1;\n        vis[row][col] = true;\n        boolean up = check(grid,row-1,col,hlt-grid.get(row).get(col));\n        boolean dw = check(grid,row+1,col,hlt-grid.get(row).get(col));\n        boolean lf = check(grid,row,col-1,hlt-grid.get(row).get(col));\n        boolean rf = check(grid,row,col+1,hlt-grid.get(row).get(col));\n        vis[row][col] = false;\n        boolean result = up || dw || lf || rf;\n        if(result){\n            dp[row][col][hlt]=1;\n        }\n        else dp[row][col][hlt]=0;\n        return result;\n    }\n    public boolean findSafeWalk(List<List<Integer>> grid, int health) {\n        int m = grid.size();\n        int n = grid.get(0).size();\n        dp = new int[m][n][health+1];\n        for(int i=0;i<m;i++){\n            for(int j=0;j<n;j++){\n                Arrays.fill(dp[i][j],-1);\n            }\n        }\n        vis = new boolean[m][n];\n        return check(grid, 0, 0, health);\n    }\n}\n```
['Dynamic Programming', 'Breadth-First Search', 'Graph', 'Java']