## 题目描述：

LeetCode 419. Battleships in a board

Given an 2D board, count how many different battleships are in it. The battleships are represented with `'X'`s, empty slots are represented with `'.'`s. You may assume the following rules:

• You receive a valid board, made of only battleships or empty slots.
• Battleships can only be placed horizontally or vertically.
• Battleships come in different sizes.
• At least one space of horizontal or vertical separates between two battleships - no adjacent battleships will be given.

Example:

```X..X
...X
...X
```

In the above board there are 2 battleships.

Your algorithm should not modify the value of the board.

## 题目大意：

• 给定的板子是有效的，只包含战舰和空白槽位。
• 战舰只能水平或者竖直放置。
• 战舰的尺寸可能不同。
• 两艘战舰之间在水平方向或者竖直方向至少包含一个空间—不会存在相邻的战舰。

## Python代码：

``````class Solution(object):
def countBattleships(self, board):
"""
:type board: List[List[str]]
:rtype: int
"""
h = len(board)
w = len(board[0]) if h else 0

ans = 0
for x in range(h):
for y in range(w):
if board[x][y] == 'X':
if x > 0 and board[x - 1][y] == 'X':
continue
if y > 0 and board[x][y - 1] == 'X':
continue
ans += 1
return ans
``````

## Python代码：

``````class Solution(object):
def countBattleships(self, board):
"""
:type board: List[List[str]]
:rtype: int
"""
vs = set()
h = len(board)
w = len(board[0]) if h else 0

def dfs(x, y):
for dx, dy in zip((1, 0, -1, 0), (0, 1, 0, -1)):
nx, ny = x + dx, y + dy
if 0 <= nx < h and 0 <= ny < w:
if (nx, ny) not in vs and board[nx][ny] == 'X':
vs.add((nx, ny))
dfs(nx, ny)

ans = 0
for x in range(h):
for y in range(w):
if (x, y) not in vs and board[x][y] == 'X':
ans += 1
vs.add((x, y))
dfs(x, y)
return ans
``````

Pingbacks已关闭。