Python solution with detailed explanation

  • 0


    Battleships in a Board

    DFS or FloodFill

    • The problem is simply to find connected components in the grid.
    class Solution(object):
        def dfs(self, board, i, j, N, M, visited):
            for x,y in ((i+1, j), (i, j+1)):
                if 0<=x<N and 0<=y<M and (x,y) not in visited and board[x][y] == "X":
                    self.dfs(board, x, y, N, M, visited)
        def countBattleships(self, board):
            :type board: List[List[str]]
            :rtype: int
            N,M = len(board), len(board[0])
            visited, cnt = set([]), 0
            for i in range(N):
                for j in range(M):
                    if board[i][j] == "X" and (i,j) not in visited:
                        self.dfs(board, i, j, N, M, visited)
                        cnt += 1
            return cnt

    Follow up: O(1) space and single pass

    • Identify the head or start of a battleship.
    • The cell is a 'X' (board[i][j] == 'X')
    • No top side neighbor, or the left neighbor is a '.' (i == 0 || board[i - 1][j] == '.')
    • No left side neighbor, or the right neighbor is a '.' (j == 0 || board[i][j - 1] == '.')

Log in to reply

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