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) 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] == '.')