# Python solution with detailed explanation

• 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):
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

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