题目描述：

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.

题目大意：

给定一个2维板，计算其中包含多少艘不同的战舰。战舰用字符'X'表示，空白槽位用'.'表示。你应该假设如下规则：

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

你的算法不应该修改board的值。

解题思路：

解法I 遍历board

由于board中的战舰之间确保有'.'隔开，因此遍历board，若某单元格为'X'，只需判断其左边和上边的相邻单元格是否也是'X'。

如果左邻居或者上邻居单元格是'X'，则说明当前单元格是左边或者上边战舰的一部分；

否则，令计数器+1

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

解法II FloodFill

遍历board，用DFS（深度优先搜索）对每一个'X'位置进行探索与标记，同时进行计数。

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

 

本文链接：http://bookshadow.com/weblog/2016/10/13/leetcode-battleships-in-a-board/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码