🔥BEATS 💯 % 🎯 | SUPER EASY AND SIMPLE🔥|
\n# Intuition\nThe problem asks for finding a safe path through a grid while maintaining a sufficient amount of health. This can be modeled as a pathfinding pro
\n# Intuition\nThe problem asks for finding a safe path through a grid while maintaining a sufficient amount of health. This can be modeled as a **pathfinding problem** where every step reduces the health, and we need to track the health at each point to decide whether to continue exploring that path.\n\n# Approach\nWe employ **Breadth-First Search (BFS)** because it helps explore the shortest path in unweighted graphs (or grids). The idea is to explore all four possible directions from each cell and only proceed if the health is positive and greater than the health in any previously visited cell.\n\n# Complexity\n- Time complexity:  \n  $$O(m \\times n)$$  \n  BFS explores each cell once, and for each cell, we attempt 4 directions.\n  \n- Space complexity:  \n  $$O(m \\times n)$$  \n  We need space for the `visited` array and the BFS queue.\n\n# Code Implementations\n\n\n```dart []\nimport \'dart:collection\';\nclass Solution {\n  bool findSafeWalk(List<List<int>> grid, int health) {\n    int m = grid.length;\n    int n = grid[0].length;\n    \n    List<List<int>> directions = [\n      [0, 1],  // right\n      [1, 0],  // down\n      [0, -1], // left\n      [-1, 0]  // up\n    ];\n    \n    Queue<List<int>> queue = Queue();\n    int initialHealth = grid[0][0] == 1 ? health - 1 : health;\n    queue.add([0, 0, initialHealth]);\n    \n    List<List<int>> visited = List.generate(m, (_) => List.filled(n, -1));\n    visited[0][0] = health;\n    \n    while (queue.isNotEmpty) {\n      List<int> current = queue.removeFirst();\n      int x = current[0], y = current[1], currentHealth = current[2];\n      \n      if (x == m - 1 && y == n - 1 && currentHealth >= 1) {\n        return true;\n      }\n      \n      for (List<int> dir in directions) {\n        int newX = x + dir[0];\n        int newY = y + dir[1];\n        \n        if (newX >= 0 && newX < m && newY >= 0 && newY < n) {\n          int newHealth = currentHealth - grid[newX][newY];\n          \n          if (newHealth >= 1 && newHealth > visited[newX][newY]) {\n            visited[newX][newY] = newHealth;\n            queue.add([newX, newY, newHealth]);\n          }\n        }\n      }\n    }\n    \n    return false;\n  }\n}\n```\n\n\n```java []\nimport java.util.*;\n\nclass Solution {\n    public boolean findSafeWalk(int[][] grid, int health) {\n        int m = grid.length;\n        int n = grid[0].length;\n\n        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};\n        Queue<int[]> queue = new LinkedList<>();\n        int initialHealth = grid[0][0] == 1 ? health - 1 : health;\n        queue.add(new int[]{0, 0, initialHealth});\n\n        int[][] visited = new int[m][n];\n        for (int[] row : visited) Arrays.fill(row, -1);\n        visited[0][0] = health;\n\n        while (!queue.isEmpty()) {\n            int[] current = queue.poll();\n            int x = current[0], y = current[1], currentHealth = current[2];\n\n            if (x == m - 1 && y == n - 1 && currentHealth >= 1) {\n                return true;\n            }\n\n            for (int[] dir : directions) {\n                int newX = x + dir[0], newY = y + dir[1];\n                if (newX >= 0 && newX < m && newY >= 0 && newY < n) {\n                    int newHealth = currentHealth - grid[newX][newY];\n                    if (newHealth >= 1 && newHealth > visited[newX][newY]) {\n                        visited[newX][newY] = newHealth;\n                        queue.add(new int[]{newX, newY, newHealth});\n                    }\n                }\n            }\n        }\n\n        return false;\n    }\n}\n```\n\n\n```javascript []\nfunction findSafeWalk(grid, health) {\n    const m = grid.length;\n    const n = grid[0].length;\n\n    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];\n    const queue = [[0, 0, grid[0][0] === 1 ? health - 1 : health]];\n    const visited = Array.from({ length: m }, () => Array(n).fill(-1));\n    visited[0][0] = health;\n\n    while (queue.length) {\n        const [x, y, currentHealth] = queue.shift();\n\n        if (x === m - 1 && y === n - 1 && currentHealth >= 1) return true;\n\n        for (const [dx, dy] of directions) {\n            const newX = x + dx, newY = y + dy;\n            if (newX >= 0 && newX < m && newY >= 0 && newY < n) {\n                const newHealth = currentHealth - grid[newX][newY];\n                if (newHealth >= 1 && newHealth > visited[newX][newY]) {\n                    visited[newX][newY] = newHealth;\n                    queue.push([newX, newY, newHealth]);\n                }\n            }\n        }\n    }\n\n    return false;\n}\n```\n\n\n```python []\nfrom collections import deque\n\nclass Solution:\n    def findSafeWalk(self, grid, health):\n        m, n = len(grid), len(grid[0])\n        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n        queue = deque([(0, 0, health - 1 if grid[0][0] == 1 else health)])\n        visited = [[-1] * n for _ in range(m)]\n        visited[0][0] = health\n\n        while queue:\n            x, y, current_health = queue.popleft()\n            if x == m - 1 and y == n - 1 and current_health >= 1:\n                return True\n\n            for dx, dy in directions:\n                new_x, new_y = x + dx, y + dy\n                if 0 <= new_x < m and 0 <= new_y < n:\n                    new_health = current_health - grid[new_x][new_y]\n                    if new_health >= 1 and new_health > visited[new_x][new_y]:\n                        visited[new_x][new_y] = new_health\n                        queue.append((new_x, new_y, new_health))\n\n        return False\n```\n\n\n```cpp []\n#include <queue>\n#include <vector>\n\nusing namespace std;\n\nclass Solution {\npublic:\n    bool findSafeWalk(vector<vector<int>>& grid, int health) {\n        int m = grid.size(), n = grid[0].size();\n        vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};\n        queue<vector<int>> q;\n        int initialHealth = grid[0][0] == 1 ? health - 1 : health;\n        q.push({0, 0, initialHealth});\n        vector<vector<int>> visited(m, vector<int>(n, -1));\n        visited[0][0] = health;\n\n        while (!q.empty()) {\n            auto current = q.front();\n            q.pop();\n            int x = current[0], y = current[1], currentHealth = current[2];\n\n            if (x == m - 1 && y == n - 1 && currentHealth >= 1) {\n                return true;\n            }\n\n            for (auto& dir : directions) {\n                int newX = x + dir[0], newY = y + dir[1];\n                if (newX >= 0 && newX < m && newY >= 0 && newY < n) {\n                    int newHealth = currentHealth - grid[newX][newY];\n                    if (newHealth >= 1 && newHealth > visited[newX][newY]) {\n                        visited[newX][newY] = newHealth;\n                        q.push({newX, newY, newHealth});\n                    }\n                }\n            }\n        }\n\n        return false;\n    }\n};\n```\n\n\n```go []\npackage main\n\nimport (\n\t"container/list"\n)\n\nfunc findSafeWalk(grid [][]int, health int) bool {\n\tm, n := len(grid), len(grid[0])\n\tdirections := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}\n\tqueue := list.New()\n\tinitialHealth := health\n\tif grid[0][0] == 1 {\n\t\tinitialHealth--\n\t}\n\tqueue.PushBack([]int{0, 0, initialHealth})\n\tvisited := make([][]int, m)\n\tfor i := range visited {\n\t\tvisited[i] = make([]int, n)\n\t\tfor j := range visited[i] {\n\t\t\tvisited[i][j] = -1\n\t\t}\n\t}\n\tvisited[0][0] = health\n\n\tfor queue.Len() > 0\n\n {\n\t\telem := queue.Remove(queue.Front()).([]int)\n\t\tx, y, currentHealth := elem[0], elem[1], elem[2]\n\n\t\tif x == m-1 && y == n-1 && currentHealth >= 1 {\n\t\t\treturn true\n\t\t}\n\n\t\tfor _, dir := range directions {\n\t\t\tnewX, newY := x+dir[0], y+dir[1]\n\t\t\tif newX >= 0 && newX < m && newY >= 0 && newY < n {\n\t\t\t\tnewHealth := currentHealth - grid[newX][newY]\n\t\t\t\tif newHealth >= 1 && newHealth > visited[newX][newY] {\n\t\t\t\t\tvisited[newX][newY] = newHealth\n\t\t\t\t\tqueue.PushBack([]int{newX, newY, newHealth})\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\n\treturn false\n}\n```\n\n\n\n```c []\n#include <stdio.h>\n#include <stdlib.h>\n\n#define MAX_QUEUE_SIZE 10000\n\ntypedef struct {\n    int x, y, health;\n} Node;\n\ntypedef struct {\n    Node queue[MAX_QUEUE_SIZE];\n    int front, rear;\n} Queue;\n\nvoid enqueue(Queue* q, int x, int y, int health) {\n    q->queue[q->rear++] = (Node){x, y, health};\n}\n\nNode dequeue(Queue* q) {\n    return q->queue[q->front++];\n}\n\nint isEmpty(Queue* q) {\n    return q->front == q->rear;\n}\n\nint findSafeWalk(int** grid, int m, int n, int health) {\n    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};\n    Queue queue = {0, 0};\n    int initialHealth = grid[0][0] == 1 ? health - 1 : health;\n    \n    enqueue(&queue, 0, 0, initialHealth);\n    \n    int** visited = (int**)malloc(m * sizeof(int*));\n    for (int i = 0; i < m; i++) {\n        visited[i] = (int*)malloc(n * sizeof(int));\n        for (int j = 0; j < n; j++) {\n            visited[i][j] = -1;\n        }\n    }\n    visited[0][0] = health;\n\n    while (!isEmpty(&queue)) {\n        Node current = dequeue(&queue);\n        int x = current.x, y = current.y, currentHealth = current.health;\n\n        if (x == m - 1 && y == n - 1 && currentHealth >= 1) {\n            return 1;\n        }\n\n        for (int i = 0; i < 4; i++) {\n            int newX = x + directions[i][0];\n            int newY = y + directions[i][1];\n\n            if (newX >= 0 && newX < m && newY >= 0 && newY < n) {\n                int newHealth = currentHealth - grid[newX][newY];\n                if (newHealth >= 1 && newHealth > visited[newX][newY]) {\n                    visited[newX][newY] = newHealth;\n                    enqueue(&queue, newX, newY, newHealth);\n                }\n            }\n        }\n    }\n    \n    for (int i = 0; i < m; i++) {\n        free(visited[i]);\n    }\n    free(visited);\n\n    return 0;\n}\n```\n\n```typescript []\nfunction findSafeWalk(grid: number[][], health: number): boolean {\n    const m = grid.length;\n    const n = grid[0].length;\n\n    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];\n    const queue: [number, number, number][] = [[0, 0, grid[0][0] === 1 ? health - 1 : health]];\n    const visited: number[][] = Array.from({ length: m }, () => Array(n).fill(-1));\n    visited[0][0] = health;\n\n    while (queue.length) {\n        const [x, y, currentHealth] = queue.shift()!;\n\n        if (x === m - 1 && y === n - 1 && currentHealth >= 1) return true;\n\n        for (const [dx, dy] of directions) {\n            const newX = x + dx;\n            const newY = y + dy;\n\n            if (newX >= 0 && newX < m && newY >= 0 && newY < n) {\n                const newHealth = currentHealth - grid[newX][newY];\n                if (newHealth >= 1 && newHealth > visited[newX][newY]) {\n                    visited[newX][newY] = newHealth;\n                    queue.push([newX, newY, newHealth]);\n                }\n            }\n        }\n    }\n\n    return false;\n}\n```\n\n---\n\n\nEach implementation follows the same BFS logic, ensuring that you explore each cell only if it\u2019s safe to proceed with sufficient health.
['C', 'C++', 'Java', 'Go', 'TypeScript', 'Python3', 'JavaScript', 'Dart']