dfs with inner bfs
Intuition\n- if all 1 cells, just a simple bfs will do.\n- with 0 cells possible, extend the front queue of bfs by dfs- exploring all 0 cells\n\n \n# Code\ncpp 
# Intuition\n- if all `1` cells, just a simple `bfs` will do.\n- with `0` cells possible, extend the front queue of `bfs` by `dfs`- exploring all `0` cells\n\n \n# Code\n```cpp []\nclass Solution {\npublic:\n    bool findSafeWalk(vector<vector<int>>& grid, int health) {\n        int m = grid.size(), n = grid.front().size();\n        queue<array<int,2>> q;\n        function<void(int,int,bool)> add;\n        using list = vector<array<int,2>>;\n        add = [&add, &q, &grid, m, n] (int r, int c, bool onlyif0) {\n            if(r >= 0 && r < m && c >= 0 && c < n && grid[r][c] != -1 && (!onlyif0 || grid[r][c] == 0)) {\n                grid[r][c] = -1;\n                q.push({r,c});\n                for(auto [dr, dc] : list{ {0,-1}, {0, 1}, {-1, 0}, {1, 0} }) {\n                    add(r+dr, c+dc, true);\n                }\n            }\n        };\n        if(grid[0][0]) --health;\n        add(0, 0, false);\n        while(health && !q.empty()) {\n            for(int i = 0, sz = q.size(); i < sz; ++i) {\n                auto [r, c] = q.front();\n                q.pop();\n                if(r == m-1 && c == n-1)\n                    return true;\n                for(auto [dr, dc] : list{ {0,-1}, {0, 1}, {-1, 0}, {1, 0} }) {\n                    add(r+dr, c+dc, false);\n                }\n            }\n            --health;\n        }\n        return false;\n    }\n};\n```
['C++']