Dijkstra ( 0/1 BFS ) Method | Beats 100% | TC: O(nxm)
\n# Complexity\n- Time complexity: O(nxm) , Notice how we\'ve skipped using a priority queue, since there are only two types of edges, we can utilise an arrayde
\n# Complexity\n- Time complexity: O(nxm) , Notice how we\'ve skipped using a priority queue, since there are only two types of edges, we can utilise an arraydeque & keep pushing the higher priority edge to front & lower priority edge to the end of the array deque.\n\n\n- Space complexity: O(nxm)\n\n# Code\n```java []\nimport java.util.*;\n\nclass Solution {\n\n    int m;\n    int n;\n    \n    private static final int[][] DIRECTIONS = {\n        {0, 1}, {0, -1}, {1, 0}, {-1, 0}\n    };\n    \n    private boolean isValid(int x, int y) {\n        return x >= 0 && y >= 0 && x < m && y < n;\n    }\n\n    public boolean findSafeWalk(List<List<Integer>> grid, int health) {\n        this.m = grid.size();\n        this.n = grid.get(0).size();\n\n        int[][] dist = new int[m][n];\n        for (int[] d : dist) {\n            Arrays.fill(d, Integer.MAX_VALUE);\n        }\n        dist[0][0] = grid.get(0).get(0);\n\n        Deque<int[]> deque = new ArrayDeque<>();\n        deque.addFirst(new int[] {dist[0][0], 0, 0});  // {currentHealthCost, x, y}\n\n        while (!deque.isEmpty()) {\n            int[] node = deque.pollFirst();\n            int currentHealthCost = node[0];\n            int x = node[1];\n            int y = node[2];\n\n            // If we reached the bottom-right corner\n            if (x == m - 1 && y == n - 1) {\n                return true;\n            }\n\n            for (int[] direction : DIRECTIONS) {\n                int newX = x + direction[0];\n                int newY = y + direction[1];\n\n                if (!isValid(newX, newY)) {\n                    continue;\n                }\n\n                int newHealthCost = currentHealthCost + grid.get(newX).get(newY);\n\n                // Skip paths that exceed the health threshold or don\'t improve the cost\n                if (newHealthCost >= health || newHealthCost >= dist[newX][newY]) {\n                    continue;\n                }\n\n                dist[newX][newY] = newHealthCost;\n\n                // If moving to (newX, newY) costs 0, add to the front of the deque; otherwise, to the back\n                if (grid.get(newX).get(newY) == 0) {\n                    deque.addFirst(new int[] {newHealthCost, newX, newY});\n                } else {\n                    deque.addLast(new int[] {newHealthCost, newX, newY});\n                }\n            }\n        }\n\n        return false;  // No path found\n    }\n}\n```
['Java']