Simple Java Solution


  • 127
    B

    Going over all cells, we can count only those that are the "first" cell of the battleship. First cell will be defined as the most top-left cell. We can check for first cells by only counting cells that do not have an 'X' to the left and do not have an 'X' above them.

    
        public int countBattleships(char[][] board) {
            int m = board.length;
            if (m==0) return 0;
            int n = board[0].length;
            
            int count=0;
            
            for (int i=0; i<m; i++) {
                for (int j=0; j<n; j++) {
                    if (board[i][j] == '.') continue;
                    if (i > 0 && board[i-1][j] == 'X') continue;
                    if (j > 0 && board[i][j-1] == 'X') continue;
                    count++;
                }
            }
            
            return count;
        }
    

  • 1
    A

    Nice solution :) for some reason my instinct was to add the most bottom-left cell. But this logic is simpler since we iterate downwards.


  • 0
    F

    Good but it only works if ships are guaranteed to be rectangle.

    Consider the following board:

       0 1 2
    0  X * X
    1  X X X
    

    the 'X' at row 0 column 2 is counted as a new ship by your code, which however is not truth.


  • 10
    B

    @FawkesLament This is actually not a valid a board. I'll make sure the rules are more clear, thanks.


  • 0
    A

    How this output is 4?

    X..X
    ...X
    X.XX
    

    I think X from 0,3 to 2,3 forms a 1 complete battleship.
    Correct if i'm wrong in understanding.


  • 9
    E

    @abhihack03 Your board and @FawkesLament board are both invalid by the problem definition which could be why it's producing unexpected results. The problem states that "At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships". In each of your boards, you have a ship adjacent to one another.


  • 2
    X

    Great solution. Although quite trivial, here is the C++ version:

    class Solution {
    public:
        int countBattleships(vector<vector<char>>& board) {
            int m = board.size();
            if (m==0) return 0;
            int n = board[0].size();
            
            int count=0;
            
            for (int i=0; i<m; i++) {
                for (int j=0; j<n; j++) {
                    if (board[i][j] == '.') continue;
                    if (i > 0 && board[i-1][j] == 'X') continue;
                    if (j > 0 && board[i][j-1] == 'X') continue;
                    count++;
                }
            }
            
            return count;
        }
    };
    
    

  • 0
    D

    I solved the proble with some way like this. Here is my c++ code:

    
    class Solution {
    public:
        int countBattleships(vector<vector<char>>& board) {
            int count = 0, m = board.size(), n = board[0].size();
            for(int i = 0; i<m; i++) {
                for(int j = 0; j<n; j++) {
                    if(board[i][j] == '.')            // empty slots
                        continue;
                    if(i+1<m && board[i+1][j] == 'X') // at the mid of a vertical battleship
                        continue;
                    if(j+1<n && board[i][j+1] == 'X') // at the mid of  a horizontal battleship
                        continue;
                    count++;                          // at the end of a battleship
                }
            }
            return count;
        }
    };
    

  • 0
    J
    This post is deleted!

  • 0
    Y
    This post is deleted!

  • 1
    X

    Please feel free to correct me if I am wrong.
    The requirement is to do the counting in ONE pass. However, in this solution, the data seems to be scanned THREE times: one for checking board[i][j], two for the condition checking of board[i+1][j], board[i][j+1].


  • 0
    P

    write in this only access up-left data.


  • 0
    H

    So brilliant thought!


  • 0

    @abhihack03 actually in the question, it says this situation will not occur, thus this situation will not be in the test case. This is my understanding.


  • 0
    G

    Your solution is so brilliant! like a refreshment to me! Really Simple!!


  • 0
    A
    This post is deleted!

  • 0

    @xingfeng.unsw said in Simple Java Solution:

    Please feel free to correct me if I am wrong.
    The requirement is to do the counting in ONE pass. However, in this solution, the data seems to be scanned THREE times: one for checking board[i][j], two for the condition checking of board[i+1][j], board[i][j+1].

    I am glad you brought an interesting question that I never thought about. As I am not coming from computer science major (please correct if am wrong), I suspect that the term "one pass" is not a concrete terminology but a sort of descriptive and intuitive phrase accepted by the programming community.

    My perception for what the term means accepted by public: a single traversal through a data structure with O(1) operations involving traversing index at each member of the data structure. So any O(1) number of accesses of any board[i'][j'] at index (i, j) within a single traversal through the board is still publicly accepted as "one pass".

    Note that this "common sense" of "one pass" certainly does NOT mean fewer time complexity (i.e., number of operations). For example, to initialize two arrays, the following code is considered as one pass

    for (i = 0; i < N: ++i) { a[i] = i*i; b[i] = sin(i); }
    

    because the initialization of a[] and b[] are independent, so we can do them simultaneously at each index i.

    However, if the initialization of each b[i] depends on the entire a[] for some reason, we have to do something like

    for (int i = 0; i < N; ++i) a[i] = i*i;
    for (int i = 0; i < N; ++i) b[i] = a[rand()%N];  
    

    Now we traversed index range [0, N) twice, but the time complexity is still O(N).

    So this "one pass" term is more about how the operations are "grouped together" with respect to traversal patterns, not referring just a single reference of each member of the traversing structure.


  • 0

    Great solution as I see many other fellow coders also posted similar solutions here.

    However, when I read this problem initially, I was struggling about how to resolve "count how many different battleships are in it". Because intuitively, I though battleship with same length will be counted as the same kind of ships...or maybe vertical ones vs horizontal ones also count differently as well.

    Until I've seen many top solutions I realized that it was asked to just count number of different battleships regardless of length or orientation.

    Maybe could @administrators clarify the problem to remove the wording "different"?

    Practically same solution to yours in C++:

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

  • 0

    @zzg_zzm Done.


  • 0
    L

    @xingfeng.unsw, i think @zzg_zzm is right, this is a one-time solution,


Log in to reply
 

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