Concise C++ Solution and general C++ solution


  • 1
    1. Concise solution O(1) space. Only left or top heads are counted;
    int countBattleships(vector<vector<char>>& board) {
        int res = 0;
        for (int i = 0; i < board.size(); i++) 
            for (int j = 0; j < board[0].size(); j++) 
                if (board[i][j] == 'X' && (i == 0 || board[i - 1][j] == '.') 
                        && (j == 0 || board[i][j - 1] == '.')) 
                    res++;    
        return res;
    }
    
    1. General Solution.
    int countBattleships(vector<vector<char>>& board) {
        if (board.empty()) return 0;
        int row = board.size(), col = board[0].size(), res = 0;
        vector<vector<bool>> visited(row, vector<bool>(col, false));
        vector<vector<int>> moves = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (visited[i][j] || board[i][j] == '.') continue;
                res++;
                visited[i][j] = true;
                for (int dir = 0; dir < 4; dir++) {
                    int x = i + moves[dir][0], y = j + moves[dir][1];
                    while (x >= 0 && x < row && y >= 0 && y < col && (visited[x][y] = board[x][y] == 'X')) {
                        x += moves[dir][0]; 
                        y += moves[dir][1];
                    }
                }
            }
        }
        return res;
    }
    

Log in to reply
 

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