419.Battleships in a Board

Tags: [matrix], [board]

Link: https://leetcode.com/problems/battleships-in-a-board/?tab=Description

Given an 2D board, count how many battleships are in it. The battleships are represented with'X's, empty slots are represented with'.'s. You may assume the following rules:

• You receive a valid board, made of only battleships or empty slots.
• Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.
• At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.

Example:

X..X
...X
...X

In the above board there are 2 battleships.

Invalid Example:

...X
XXXX
...X

This is an invalid board that you will not receive - as battleships will always have a cell separating between them.

Follow up:
Could you do it in one-pass, using onlyO(1) extra memory and without modifying the value of the board?

Solution: traverse matrix

class Solution(object):
    def countBattleships(self, board):
        """
        :type board: List[List[str]]
        :rtype: int
        """
        if not board:
            return 0

        row_nums = len(board)
        col_nums = len(board[0])

        counter = 0
        for row in xrange(row_nums):
            for col in xrange(col_nums):
                if board[row][col] == '.':
                    continue
                if (board[row][col] == 'X') and\
                   ((row - 1 < 0 or board[row - 1][col] == '.') and (col - 1 < 0 or board[row][col - 1] == '.')):
                       counter += 1

        return counter

Revelation:

• Only when, current slot is 'X', and its left and its top is 'empty', the counter will be increased by 1.

Note:

• Time complexity = O(n * m), n is the number of rows of the given board, m is the number of the columns of the given board.