**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