0419：棋盘上的战舰（★）

力扣第 419 题

题目

给你一个大小为 m x n 的矩阵 board 表示棋盘，其中，每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' ，返回在棋盘 board 上放置的 舰队 的数量。

舰队 只能水平或者垂直放置在 board 上。换句话说，舰队只能按 1 x k（1 行，k 列）或 k x 1（k 行，1 列）的形状放置，其中 k 可以是任意大小。两个舰队之间至少有一个水平或垂直的空格分隔 （即没有相邻的舰队）。

示例 1：

输入：board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
输出：2

示例 2：

输入：board = [["."]]
输出：0

提示：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] 是 '.' 或 'X'

进阶：你可以实现一次扫描算法，并只使用 O(1) 额外空间，并且不修改 board 的值来解决这个问题吗？

分析

类似 0200 岛屿问题，不过战舰只能是长方形，所以遍历找到左上顶点即可。

解答

1
2
3
4
5
6
7
8

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        m,n = len(board),len(board[0])
        res = 0
        for i,j in product(range(m),range(n)):
            if board[i][j]=='X' and not (i and board[i-1][j]=='X') and not (j and board[i][j-1]=='X'):
                res += 1
        return res

33 ms