Hi community, I came across below leetcode problem:

URL: https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/description/

Statement: You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m — 1, n — 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

Below mentioned DFS solution is an AC for the problem

My doubt: In my code I just made tiny changes: I called help() for cell at 0,0 instead of cell at grid.size()-1,grid[0].size()-1, and my code fails

Note: In my code I updated the implementation (base case and manhattan optimization) of help() accordingly

Is the solution dependent on direction of dfs, or the test cases might have been weak ??

class Solution { public: int dp[42][42][1609]; const static int MAX = 1e7;

int shortestPath(vector<vector<int>>& grid, int k) {
    return help(grid, grid.size() - 1, grid[0].size() - 1, k, k);
}

int help(vector<vector<int>>& grid, int x, int y, int z, int k){

    //Reached destination
    if(x == 0 && y  == 0)return 0;

    //Already visited/calculated
    if(dp[x][y][z]) return dp[x][y][z];

    //Cant remove any more obstacles
    if(grid[x][y] == 1 && z == 0)return MAX;

    //Manhattan optimization
    if(z >= x + y)return dp[x][y][z] = x+y;

    //Make sure to take direction left and up before right and top
    vector<vector<int>> dirs = {{-1,0}, {0,-1}, {1,0}, {0,1}};

    //Setting dp[x][y][z] to MAX so that it does not gets calculated again 
    dp[x][y][z] = MAX;

    for(auto dir:dirs){
        //DFS valid condition
        if(x + dir[0] >= 0 && x + dir[0] < grid.size() && y + dir[1] >=0 && y + dir[1] < grid[0].size() ){
            dp[x][y][z] = min(dp[x][y][z], help(grid, x + dir[0], y + dir[1], z - grid[x][y], k) + 1);
        }
    }
    //If not possible
    if(z == k && x == grid.size() - 1 && y == grid[0].size() - 1 && dp[x][y][z] == MAX)return -1;
    return dp[x][y][z];

}
};