Solution passed custom testcase but failed on submission, WHY?


  • 0
    R

    Below is my first solution to this problem using DFS. It could pass my custom test case but failed on submission.

    Submission Result: Wrong Answer More Details 
    
    Input:
    [[0,1]]
    Output:
    11
    Expected:
    4
    

    Although it is not a perfect solution, but I still don't see what's the root cause for the failure. I do not use any global or static variables. Could anyone help to point the suspicious code?

    class Solution {
    private:
        int computePerimeter(const vector<vector<int>>& grid, size_t row, size_t col) {
            int result = 0;
    
            if(row == 0) ++result;                 // topmost
            else if(!grid[row-1][col]) ++result;   // up
    
            if(col == 0) ++result;                 // leftmost
            else if(!grid[row][col-1]) ++result;   // left
    
            if(row == grid.size()-1) ++result;     // bottom
            else if(!grid[row+1][col]) ++result;   // down
    
            if(col == grid[0].size()-1) ++result;  // rightmost
            else if(!grid[row][col+1]) ++result;   // right
    
            //cout << "row=" << row << ";col=" << col << ";result=" << result << endl;
            return result;
        }
    
        int BFS(const vector<vector<int>>& grid, size_t row, size_t col) {
            vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
            
            int result = 0;
    
            queue<pair<size_t, size_t>> queue;
            queue.push(make_pair(row, col));
            
            while(!queue.empty()) {
                size_t r, c;
                std::tie(r, c) = queue.front();
                queue.pop();
    
                if(visited[r][c]) continue;
    
                visited[r][c] = true;
    
                result += computePerimeter(grid, r, c);
    
                // push all adjacent landcells to queue
                if(r != 0 && grid[r-1][c] && !visited[r-1][c]) queue.push(make_pair(r-1, c));              // move up
                if(r+1 < grid.size() && grid[r+1][c] && !visited[r+1][c]) queue.push(make_pair(r+1, c));   // move down
                if(c != 0 && grid[r][c-1] && !visited[r][c-1]) queue.push(make_pair(r, c-1));              // move left
                if(+1 < grid[0].size() && grid[r][c+1] && !visited[r][c+1]) queue.push(make_pair(r, c+1)); // move right
            }
    
            return result;
        }
    
    public:
        int islandPerimeter(vector<vector<int>>& grid) {
            if(grid.empty()) return 0;
    
            // find 1st land cell
            bool find = false;
            int row = 0;
            int col = 0;
            while(!find && row < grid.size()) {
                while(!find && col < grid[0].size()) {
                    if(grid[row][col]) { find = true; break; }
                    else ++col;
                }
    
                if(find) break;
                else ++row;
            }
    
            if(!find) return 0;
    
            return BFS(grid, row, col);
        }
    };
    
    

Log in to reply
 

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