battleships_in_a_board

View Source

 1# @leet start
 2class Solution:
 3    def countBattleships(self, board: list[list[str]]) -> int:
 4        """
 5        This question asks us to count the number of battleships in a board
 6        where a battleship is horizontal or vertical (1 x k) or (k x 1).
 7
 8        We can do this straightforwardly with just a dfs. Since battleships
 9        are guaranteed not to be next to each other, a dfs works for this Q.
10        """
11        visited = set()
12        m, n = len(board), len(board[0])
13
14        def inbounds(y, x):
15            return 0 <= y < m and 0 <= x < n
16
17        def dfs(y, x):
18            if not inbounds(y, x) or (y, x) in visited or board[y][x] == ".":
19                return
20            visited.add((y, x))
21            dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
22            for dy, dx in dirs:
23                dfs(dy + y, dx + x)
24
25        count = 0
26        for y in range(m):
27            for x in range(n):
28                if board[y][x] == "X" and (y, x) not in visited:
29                    count += 1
30                    dfs(y, x)
31        return count
32
33
34# @leet end
35
36
37def test():
38    assert 2 + 2 == 4

class Solution: View Source

 3class Solution:
 4    def countBattleships(self, board: list[list[str]]) -> int:
 5        """
 6        This question asks us to count the number of battleships in a board
 7        where a battleship is horizontal or vertical (1 x k) or (k x 1).
 8
 9        We can do this straightforwardly with just a dfs. Since battleships
10        are guaranteed not to be next to each other, a dfs works for this Q.
11        """
12        visited = set()
13        m, n = len(board), len(board[0])
14
15        def inbounds(y, x):
16            return 0 <= y < m and 0 <= x < n
17
18        def dfs(y, x):
19            if not inbounds(y, x) or (y, x) in visited or board[y][x] == ".":
20                return
21            visited.add((y, x))
22            dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
23            for dy, dx in dirs:
24                dfs(dy + y, dx + x)
25
26        count = 0
27        for y in range(m):
28            for x in range(n):
29                if board[y][x] == "X" and (y, x) not in visited:
30                    count += 1
31                    dfs(y, x)
32        return count

def countBattleships(self, board: list[list[str]]) -> int: View Source

 4    def countBattleships(self, board: list[list[str]]) -> int:
 5        """
 6        This question asks us to count the number of battleships in a board
 7        where a battleship is horizontal or vertical (1 x k) or (k x 1).
 8
 9        We can do this straightforwardly with just a dfs. Since battleships
10        are guaranteed not to be next to each other, a dfs works for this Q.
11        """
12        visited = set()
13        m, n = len(board), len(board[0])
14
15        def inbounds(y, x):
16            return 0 <= y < m and 0 <= x < n
17
18        def dfs(y, x):
19            if not inbounds(y, x) or (y, x) in visited or board[y][x] == ".":
20                return
21            visited.add((y, x))
22            dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
23            for dy, dx in dirs:
24                dfs(dy + y, dx + x)
25
26        count = 0
27        for y in range(m):
28            for x in range(n):
29                if board[y][x] == "X" and (y, x) not in visited:
30                    count += 1
31                    dfs(y, x)
32        return count

This question asks us to count the number of battleships in a board where a battleship is horizontal or vertical (1 x k) or (k x 1).

We can do this straightforwardly with just a dfs. Since battleships are guaranteed not to be next to each other, a dfs works for this Q.

def test(): View Source

38def test():
39    assert 2 + 2 == 4