BFS implementation for leetcode problem fails one test case

Question

I am trying to solve a LeetCode problem (1219. Path with Maximum Gold) with BFS approach

Statement:

In a gold mine grid of size m x n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty. Return the maximum amount of gold you can collect under the conditions: Every time you are located in a cell you will collect all the gold in that cell. From your position, you can walk one step to the left, right, up, or down. You can't visit the same cell more than once. Never visit a cell with 0 gold. You can start and stop collecting gold from any position in the grid that has some gold.

class Solution {
    public int getMaximumGold(int[][] grid) {
        int max = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] != 0) {
                    boolean isVis[][] = new boolean[grid.length][grid[0].length];
                    int val = bfs(i, j, isVis, grid);
                    max = Math.max(max, val);
                }
            }
        }
        return max;
    }

    public int bfs(int r, int c, boolean isVis[][], int[][] grid) {
        Queue<int[]> q = new LinkedList<>();

        q.add(new int[] { r, c, grid[r][c] });
        int max = grid[r][c];

        isVis[r][c] = true;

        while (!q.isEmpty()) {
            int path[] = q.poll();

            int[][] arr = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

            for (int i = 0; i < 4; i++) {
                int rc = path[0] + arr[i][0];
                int cc = path[1] + arr[i][1];

                if (rc < 0 || cc < 0 || rc >= grid.length || cc >= grid[0].length || isVis[rc][cc]
                        || grid[rc][cc] == 0) {
                    max = Math.max(max, path[2]);
                    continue;
                }

                int sum = grid[rc][cc] + path[2];
                isVis[rc][cc] = true;

                q.add(new int[] { rc, cc, sum });
            }
        }
        return max;
    }
}

I am able get execute 28 test case , the below one is failing

int grid[][] = {{1,0,7,0,0,0},{2,0,6,0,1,0},{3,5,6,7,4,2},{4,3,1,0,2,0},{3,0,5,0,20,0}};

Expected answer is 60 my code gives 54 I could not find the issue in my code. Any one could help on finding the issue with the above code

I have not debugged your code. I do think the choice to use BFS in this case likely makes the problem harder than necessary. BFS is generally more complicated than DFS, so there needs to be a reason to justify its use. Consider that the question is asking for the highest value path, and the value of a path only increases as it is explored. So, you have to fully explore every path. BFS is not letting you take any shortcuts. — John Angland
– John Angland, Commented May 2, 2024 at 15:39
Yes John Thank for your inputs I will try it using DFS since I started to explore the graphs I taught of using BFS. let me know what is the best use case for BFS that would me for choosing the algorithms — Karthikeyan
– Karthikeyan, Commented May 2, 2024 at 15:51

Unmitigated · Accepted Answer · 2024-05-02 21:23:49Z

2

This is a standard use case for recursion with backtracking.

public int getMaximumGold(int[][] grid) {
    int ans = 0;
    for (int r = 0; r < grid.length; r++)
        for (int c = 0; c < grid[r].length; c++)
            ans = Math.max(ans, dfs(grid, r, c));
    return ans;
}
private int dfs(int[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[r].length || grid[r][c] == 0)
        return 0;
    int curr = grid[r][c], best = 0;
    grid[r][c] = 0;
    for (var move : new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}})
        best = Math.max(best, dfs(grid, r + move[0], c + move[1]));
    return (grid[r][c] = curr) + best;
}

answered May 2, 2024 at 21:23

Unmitigated

91.4k12 gold badges102 silver badges109 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

ILMTitan · Accepted Answer · 2024-05-02 16:21:59Z

1

I think the problem is your isVis array being global when it needs to be local to the path you are currently exploring.

Consider a simple 2x2 grid {{1,1}, {1,1}}. I suspect your code will return 3, while the correct answer is 4. This is because you will start at 0,0, then check a path going to 1,0 and a path going 0,1. But because isVis is global, neither path will be allowed to go to the cell visited by the other path. So one will get 1,1, but won't be able to path beyond that.

answered May 2, 2024 at 16:21

ILMTitan

11k3 gold badges32 silver badges48 bronze badges

1 Comment

Karthikeyan Over a year ago

yes I got the issue from your code I thinking how to make a local path visited

Collectives™ on Stack Overflow

BFS implementation for leetcode problem fails one test case

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related