Battleships in a Board

Question

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 only O(1) extra memory and without modifying the value of the board?

Tags

• Array

Thought

Two algorithms.

• Use stack for DFS search and count for each DFS search
• Traversal through the matrix

First algorithm: When find an element which is 'X' in the matrix, do a DFS search to add all the neighboring elements into visited set and add the count with 1. This efficiency of this solution is very slow.

Second algorithm: https://discuss.leetcode.com/topic/64834/python-solution Loop through the whole matrix directly.

Code

First algorithm:

class Solution(object):
    def countBattleships(self, board):
        """
        :type board: List[List[str]]
        :rtype: int
        """
        def getNeighbor(e, visited, height, width):
            (x, y) = e
            result = []
            for (i, j) in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                if i < 0 or i > height - 1:
                    continue
                if j < 0 or j > width - 1:
                    continue
                if (i, j) in visited:
                    continue
                result.append((i, j))
            return result

        height = len(board)
        width = len(board[0])
        count = 0
        visited = set()
        for i in xrange(height):
            for j in xrange(width):
                if (i, j) in visited:
                    continue
                if board[i][j] == '.':
                    visited.add((i, j))
                else:
                    stack = [(i, j)]
                    while stack:
                        e = stack.pop()
                        neighbors = getNeighbor(e, visited, height, width)
                        for item in neighbors:
                            visited.add(item)
                            x, y = item
                            if board[x][y] == 'X':
                                stack.append(item)
                    count += 1

        return count

Second algorithm:

class Solution(object):
    def countBattleships(self, board):
        """
        :type board: List[List[str]]
        :rtype: int
        """
        if len(board) == 0: return 0
        m, n = len(board), len(board[0])
        count = 0
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'X' and (i == 0 or board[i-1][j] == '.') and (j == 0 or board[i][j-1] == '.'):
                    count += 1
        return count