Easy repetitive DP until stable No BFS/DFS/Dijkstra
Complexity\n- Time complexity: O(zNM), where z = the number of loops we have to make until the health DP matrix is stable.\n\n- Space complexity: O(N*M)\n\n# Co
# Complexity\n- Time complexity: $$O(z*N*M)$$, where z = the number of loops we have to make until the health DP matrix is stable.\n\n- Space complexity: $$O(N*M)$$\n\n# Code\n```cpp []\n#include <bits/stdc++.h>\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        if(health >= M+N) return true;\n        vector<vector<int>> dp(M, vector<int>(N, INT_MIN));\n        dp[0][0] = health-(grid[0][0]==1);\n        for(int i = 1; i < N; i++) {\n            dp[0][i] = dp[0][i-1] - (grid[0][i] == 1);\n        }\n        for(int j = 1; j < M; j++) {\n            dp[j][0] = dp[j-1][0] - (grid[j][0] == 1);\n        }\n        // Initial max health from(0,0) to(i,j) if we can only move down and right\n        for(int i = 1; i < M; i++) {\n            for(int j = 1; j < N; j++) {\n                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) - (grid[i][j] == 1);\n            }\n        }\n        auto cmax = [&](int& a, int b) -> const char {\n            // returns true if there is a change that happens\n            if(b > a) {\n                a = b; return 1;\n            }\n            return 0;\n        };\n        bool change = true;\n        while(change) { // From the testcases and constraints, this loops at most 5 times.\n            change = false;\n            for(int i = 0; i < M; i++) {\n                for(int j = 0; j < N; j++) {\n                    // Here, we consider left right down up until no change happens which means we\'ve reached a stable position.\n                    if(i > 0) {\n                        if(cmax(dp[i][j], dp[i-1][j] - (grid[i][j] == 1))) change = true;\n                    }\n                    if(j > 0) {\n                        if(cmax(dp[i][j], dp[i][j-1] - (grid[i][j] == 1))) change = true;\n                    }\n                    if(i+1 < M) {\n                        if(cmax(dp[i][j], dp[i+1][j] - (grid[i][j] == 1))) change = true;\n                    }\n                    if(j+1 < N) {\n                        if(cmax(dp[i][j], dp[i][j+1] - (grid[i][j] == 1))) change = true;\n                    }\n                }\n            }\n        }\n        return dp.back().back() > 0;\n    }\n};\n```
['C++']