Java | Djikstra -> 0-1 BFS
Using Djikstra\'s algorithm \nTime Complexity: O(V + ElogV)\n\n    public boolean findSafeWalk(List<List<Integer>> grid, int health) {\n        int[][] score = 
Using Djikstra\'s algorithm \nTime Complexity: O(V + ElogV)\n```\n    public boolean findSafeWalk(List<List<Integer>> grid, int health) {\n        int[][] score = new int[grid.size()][grid.get(0).size()];\n        int[][] mat = new int[grid.size()][grid.get(0).size()];\n        int[][] directions = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};\n        \n        for (int[] r : score) {\n            Arrays.fill(r, -3000);\n        }\n        \n        for (int i = 0; i < grid.size(); i++) {\n            for (int j = 0; j < grid.get(0).size(); j++) {\n                mat[i][j] = grid.get(i).get(j);\n            }\n        }\n        \n        score[0][0] = (mat[0][0] == 1) ? -1 : 0;\n        \n        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {\n           public int compare(int[] left, int[] right) {\n               return right[2] - left[2];\n           } \n        });\n        \n        pq.add(new int[]{0, 0, score[0][0]});\n        \n        while (!pq.isEmpty()) {\n            int[] top = pq.poll();\n            int r = top[0];\n            int c = top[1];\n            int val = top[2];\n            \n            for (int[] d : directions) {\n                int nr = r + d[0];\n                int nc = c + d[1];\n                if (nr < 0 || nc < 0 || nr == grid.size() || nc == grid.get(0).size()) {\n                    continue;\n                }\n                int newVal = (mat[nr][nc] == 1) ? val - 1 : val;\n                if (newVal <= score[nr][nc]) {\n                    continue;\n                }\n                score[nr][nc] = newVal;\n                pq.add(new int[]{nr, nc, newVal});\n            }\n        }\n        \n        return health + score[grid.size() - 1][grid.get(0).size() - 1] > 0;\n    }\n```\n\n\nUsing 0-1 BFS \nSince the nodes can have only 2 states (0 and 1), Djikstra\'s solution can be improved by replacing the priority queue with a dequeue. See https://cp-algorithms.com/graph/01_bfs.html#algorithm\nTime Complexity: O(V + E)\n```\n    public boolean findSafeWalk(List<List<Integer>> grid, int health) {\n        int[][] score = new int[grid.size()][grid.get(0).size()];\n        int[][] mat = new int[grid.size()][grid.get(0).size()];\n        int[][] directions = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};\n        \n        for (int[] r : score) {\n            Arrays.fill(r, -3000);\n        }\n        \n        for (int i = 0; i < grid.size(); i++) {\n            for (int j = 0; j < grid.get(0).size(); j++) {\n                mat[i][j] = grid.get(i).get(j);\n            }\n        }\n        \n        score[0][0] = (mat[0][0] == 1) ? -1 : 0;\n        \n        Deque<int[]> queue = new ArrayDeque<int[]>();\n        \n        queue.add(new int[]{0, 0, score[0][0]});\n        \n        while (!queue.isEmpty()) {\n            int[] top = queue.poll();\n            int r = top[0];\n            int c = top[1];\n            int val = top[2];\n            \n            for (int[] d : directions) {\n                int nr = r + d[0];\n                int nc = c + d[1];\n                if (nr < 0 || nc < 0 || nr == grid.size() || nc == grid.get(0).size()) {\n                    continue;\n                }\n                int newVal = (mat[nr][nc] == 1) ? val - 1 : val;\n                if (newVal <= score[nr][nc]) {\n                    continue;\n                }\n                score[nr][nc] = newVal;\n                if (mat[nr][nc] == 1) {\n                    queue.addLast(new int[]{nr, nc, newVal});\n                } else {\n                    queue.addFirst(new int[]{nr, nc, newVal});\n                }\n            }\n        }\n        \n        return health + score[grid.size() - 1][grid.get(0).size() - 1] > 0;\n    }\n```\n
['Breadth-First Search', 'Java']