Dijkstra's
I tried DFS but got TLE (I wrongly thought 50x50 is small enough). \n\nSo, we need to approach this as the minimum distance problem, and use Dijkstra\'s.\n\n> N
I tried DFS but got TLE (I wrongly thought 50x50 is small enough). \n\nSo, we need to approach this as the minimum distance problem, and use Dijkstra\'s.\n\n> Note: a regular BFS also works as the input is not that large.\n> Dijkstra\'s runtime is ~50 ms, and BFS is ~120 ms.\n> \n\nWe use `cnt` to track the largest health we can have when we reach cell `i, j`.\n\n**C++**\n```cpp\nbool findSafeWalk(vector<vector<int>>& g, int health) {\n    int m = g.size(), n = g[0].size(), cnt[51][51] = {};\n    priority_queue<array<int, 3>> pq;\n    pq.push({health - g[0][0], 0, 0});\n    while (!pq.empty()) {\n        auto [h, i, j] = pq.top(); pq.pop();\n        if (i == m - 1 && j == n - 1)\n            return true;\n        for (auto [dx, dy] : vector<pair<int, int>>{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {\n            int x = i + dx, y = j + dy;\n            if (min(x, y) >= 0 && x < m && y < n && cnt[x][y] < h - g[x][y]) {\n                cnt[x][y] = h - g[x][y];\n                pq.push({h - g[x][y], x, y});\n            }\n        }\n    }\n    return false;\n}\n```
['C']