using pairs of pair datatype of queue
Intuition\n Describe your first thoughts on how to solve this problem. \nTo solve this problem, we need to find a path from the top-left corner to the bottom-ri
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo solve this problem, we need to find a path from the top-left corner to the bottom-right corner of a binary matrix. The path should ensure that our health remains positive at all times. Unsafe cells reduce our health, and we can move up, down, left, or right to adjacent cells. A Breadth-First Search (BFS) approach is suitable here as it will explore all possible paths level by level and help us find whether there is a feasible path with health remaining positive.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Initialization:** Use BFS to explore all possible paths from the starting cell (0,0) to the ending cell (m-1, n-1). Initialize the queue with the starting position and health adjusted for the first cell.\n\n2. **Visited Tracking:** Maintain a visited matrix to keep track of the maximum health remaining when reaching each cell to avoid redundant work and prevent revisiting cells with lower health.\n\n3. **BFS Traversal:**\n- Dequeue the current cell and its remaining health.\n- Check if the current cell is the destination and has positive health. If yes, return true.\n- For each direction (right, down, left, up), compute the next cell\u2019s position and check if it\u2019s within bounds.\n- Compute the new health value after moving to the next cell.\n- If the new health is positive and greater than what has been recorded for that cell, update the visited matrix and enqueue the new cell.\n\n4. Termination: If the queue is empty and the destination hasn\u2019t been reached with positive health, return false.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    bool findSafeWalk(vector<vector<int>>& grid, int health) {\n        int m = grid.size();\n        int n = grid[0].size();\n        int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};\n        queue<pair<pair<int,int>,int>>q;\n        q.push({{0,0},health-grid[0][0]});\n        vector<vector<int>> visited(m, vector<int>(n, -1));\n        visited[0][0] = health;\n        \n        while (!q.empty()) {\n            auto [pos, currHealth] = q.front();\n            q.pop();\n            int x=pos.first;\n            int y=pos.second;\n            if (x == m - 1 && y == n - 1 && currHealth>0) {\n                return true;\n            }\n            for(int i=0;i<4;i++){\n                int newX=x+directions[i][0];\n                int newY=y+directions[i][1];\n                if(newX >=0 && newY>=0 && newX<m && newY<n){\n                    int newHealth=currHealth - grid[newX][newY];\n                    if(newHealth>0 && newHealth>visited[newX][newY]){\n                        visited[newX][newY]=newHealth;\n                        q.push({{newX,newY},newHealth});\n                    }\n                }\n            } \n        }\n        return false;\n    }\n};\nauto init=[](){\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['C++']