Python solution with detailed explanation


  • 0
    G

    Solution

    Battleships in a Board https://leetcode.com/problems/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):
            visited.add((i,j))
            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)
            return
        
        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] == '.')
      https://discuss.leetcode.com/topic/65025/4ms-java-optimized-code

Log in to reply
 

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