customized test correct but submission wrong answer


  • 0
    E

    When I submit, I got answer -1 for this test case
    [[7339,0],[191,4835],[2529,0],[966,4605],[6704,0],[7947,0],[3280,7050],[0,7140],[9103,2678]]
    however, when I copy the input to customized test case and ran it, I got the correct answer 48.

    Is it a bug? Please help?

    
    class Solution {
    public:
        int cutOffTree(vector<vector<int>>& forest) {
            
            int h = forest.size();
            int w = forest[0].size();
            
            vector<vector<int>> cache = vector<vector<int>>{ {1, 0, 0} };
    
            for (int i = 0; i < forest.size(); i++)
                for (int j = 0; j < forest[0].size(); j++)
                    if(forest[i][j] > 1)
                        cache.push_back({forest[i][j], i, j});
            
            sort(cache.begin(), cache.end(), [](const vector<int>& v1, const vector<int>& v2) -> bool
                 {
                     return v1[0] < v2[0];
                 });
            
            int res = 0;
            
            for (int i = 0; i < cache.size()-1; i++)
            {
                vector<int> start = {cache[i][1], cache[i][2], 0};
                vector<int> end = {cache[i+1][1], cache[i+1][2]};
                
                int steps = bfs(forest, start, end);
                
                if (steps == -1)
                    return -1;
                res += steps;
    
            }
            return res;
        }
        
        int bfs(vector<vector<int>>& forest, vector<int>& start, vector<int>& end)
        {
            //cout << "start: " + start[0] << " " << start[1] << " end:" << end[0] << " " << end[1] << endl;
            
            if(start[0] == end[0] && start[1] == end[1])
                return 0;
            
            deque<vector<int>> queue;
            
            queue.push_back(start);
            
            set<int> visited;
            
            int positions[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
            
            while(queue.size() > 0)
            {
                vector<int> point = queue[0];
                queue.pop_front();
                for(int i = 0; i < 4; i++)
                {
                    int nr = point[0] + positions[i][0];
                    int nc = point[1] + positions[i][1];
                    
                    //cout << point[0] << " " << point[1] << " " << point[2] << " " << nr << " " << nc << endl;
                    if (isValid(forest, nr, nc))
                    {
                        if (nr == end[0] && nc == end[1])
                            return point[2] + 1;
                        
                        int key = nr * forest[0].size() + nc;
                        
                        //cout << "key " << key << " " << (visited.find(key) == visited.end()) << endl;
                        
                        if (visited.find(key) == visited.end())
                        {
                            visited.insert(key);
                            vector<int> np = {nr, nc, point[2] + 1};
                            queue.push_back(np);
                        }
                    }
                }
            }
            
            return -1;
        }
        
        bool isValid(vector<vector<int>>& forest, int r, int c)
        {
            if (c < 0 || r < 0 || r >= forest.size() || c > forest[0].size())
                return false;
            return forest[r][c] != 0;
        }
        
    };
    

  • 0
    M

    Did you already read what the FAQ says about this?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.