C++ 1 pass, O(1) memory solution


  • 0
    B

    General Idea: find the heads of all the battle ships.
    When a 'X' cell with '.' in both its upper and left cell, we count it as one head of a ship.

    int countBattleships(vector<vector<char>>& board)
    {
        int m = board.size();
        if(!m) return 0;
        int n = board[0].size();
        
        int cnt = 0;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(board[i][j] == 'X' 
                  && (i == 0 || board[i - 1][j] == '.') 
                  && (j == 0 || board[i][j - 1] == '.')) cnt++;
            }
        }
        return cnt;
    }

Log in to reply
 

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