419. 甲板上的战舰

题目描述

输入一个 m x n 的字符矩阵 board。每格是 'X'（属于某艘战舰）或 '.'（空）。

每艘战舰占据同一行的连续若干格，或者同一列的连续若干格，即形状为 1 x k 或 k x 1，k 可以是任意正整数。

任意两艘战舰不会在上下左右方向上相邻，中间至少隔着一个空格。

返回棋盘上战舰的总数。

示例 1

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

解释：左上角单独一格是一艘，最右一列竖着的三格是另一艘，共 2 艘。

示例 2

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

解释：棋盘上没有 'X'，所以是 0。

数据范围

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

进阶：能否只遍历一次、只用 O(1) 额外空间，并且不改动 board 的内容？

解题思路：枚举战舰起点

每艘战舰只数它的“船头”：最上方、最左边的那个格子。一个 X 格子如果上方或左边也是 X，它就是某艘船的身体，跳过；否则它是船头，计数加一。一遍扫描、不改棋盘、O(1) 额外空间。

为什么正确

每艘战舰恰好有一个格子的上方和左边都不是 X。

复杂度分析

时间 O(mn)，空间 O(1)。

易错点

只看上和左，不要看下和右；判断前要先检查 i > 0、j > 0，避免越界。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

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

class Solution {
    public int countBattleships(char[][] board) {
        int count = 0;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] != 'X') {
                    continue;
                }
                if (i > 0 && board[i - 1][j] == 'X') {
                    continue;
                }
                if (j > 0 && board[i][j - 1] == 'X') {
                    continue;
                }
                count++;
            }
        }
        return count;
    }
}

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int count = 0;
        for (int i = 0; i < (int)board.size(); i++) {
            for (int j = 0; j < (int)board[0].size(); j++) {
                if (board[i][j] != 'X') {
                    continue;
                }
                if (i > 0 && board[i - 1][j] == 'X') {
                    continue;
                }
                if (j > 0 && board[i][j - 1] == 'X') {
                    continue;
                }
                count++;
            }
        }
        return count;
    }
};

func countBattleships(board [][]byte) int {
	count := 0
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[0]); j++ {
			if board[i][j] != 'X' {
				continue
			}
			if i > 0 && board[i-1][j] == 'X' {
				continue
			}
			if j > 0 && board[i][j-1] == 'X' {
				continue
			}
			count++
		}
	}
	return count
}

var countBattleships = function(board) {
    let count = 0;
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (board[i][j] !== 'X') {
                continue;
            }
            if (i > 0 && board[i - 1][j] === 'X') {
                continue;
            }
            if (j > 0 && board[i][j - 1] === 'X') {
                continue;
            }
            count++;
        }
    }
    return count;
};

function countBattleships(board: string[][]): number {
    let count = 0;
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (board[i][j] !== 'X') {
                continue;
            }
            if (i > 0 && board[i - 1][j] === 'X') {
                continue;
            }
            if (j > 0 && board[i][j - 1] === 'X') {
                continue;
            }
            count++;
        }
    }
    return count;
}

载入编辑器，自己跑一遍 →

其他解法

标记法数连通块，直观但要额外空间；枚举起点只数每艘船的左上角，一次扫描且不占额外空间。

解法 2：遍历并标记整艘船时间 O(m·n)，空间 O(m·n)

按行扫描棋盘。遇到未标记的 'X' 时计数加 1。因为战舰只能横放或竖放，从这里向右、向下把连续的 'X' 全部标记为已访问。之后再遇到这些格子就跳过。

思路就是“数连通块”，最容易想到。需要 O(m·n) 的标记数组，或者修改原棋盘。

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        m, n = len(board), len(board[0])
        seen = [[False] * n for _ in range(m)]
        count = 0
        for i in range(m):
            for j in range(n):
                if board[i][j] != 'X' or seen[i][j]:
                    continue
                count += 1
                # 战舰是一条横线或竖线：沿右、下两个方向把整艘船标记掉
                seen[i][j] = True
                k = j + 1
                while k < n and board[i][k] == 'X':
                    seen[i][k] = True
                    k += 1
                k = i + 1
                while k < m and board[k][j] == 'X':
                    seen[k][j] = True
                    k += 1
        return count

class Solution {
    public int countBattleships(char[][] board) {
        int m = board.length, n = board[0].length;
        boolean[][] seen = new boolean[m][n];
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] != 'X' || seen[i][j]) continue;
                count++;
                seen[i][j] = true;
                for (int k = j + 1; k < n && board[i][k] == 'X'; k++) seen[i][k] = true;
                for (int k = i + 1; k < m && board[k][j] == 'X'; k++) seen[k][j] = true;
            }
        }
        return count;
    }
}

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int m = board.size(), n = board[0].size();
        vector<vector<bool>> seen(m, vector<bool>(n, false));
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] != 'X' || seen[i][j]) continue;
                count++;
                seen[i][j] = true;
                for (int k = j + 1; k < n && board[i][k] == 'X'; k++) seen[i][k] = true;
                for (int k = i + 1; k < m && board[k][j] == 'X'; k++) seen[k][j] = true;
            }
        }
        return count;
    }
};

func countBattleships(board [][]byte) int {
	m, n := len(board), len(board[0])
	seen := make([][]bool, m)
	for i := range seen {
		seen[i] = make([]bool, n)
	}
	count := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if board[i][j] != 'X' || seen[i][j] {
				continue
			}
			count++
			seen[i][j] = true
			for k := j + 1; k < n && board[i][k] == 'X'; k++ {
				seen[i][k] = true
			}
			for k := i + 1; k < m && board[k][j] == 'X'; k++ {
				seen[k][j] = true
			}
		}
	}
	return count
}

var countBattleships = function(board) {
    const m = board.length, n = board[0].length;
    const seen = Array.from({ length: m }, () => new Array(n).fill(false));
    let count = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] !== 'X' || seen[i][j]) continue;
            count++;
            seen[i][j] = true;
            for (let k = j + 1; k < n && board[i][k] === 'X'; k++) seen[i][k] = true;
            for (let k = i + 1; k < m && board[k][j] === 'X'; k++) seen[k][j] = true;
        }
    }
    return count;
};

function countBattleships(board: string[][]): number {
    const m = board.length, n = board[0].length;
    const seen: boolean[][] = Array.from({ length: m }, () => new Array(n).fill(false));
    let count = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] !== 'X' || seen[i][j]) continue;
            count++;
            seen[i][j] = true;
            for (let k = j + 1; k < n && board[i][k] === 'X'; k++) seen[i][k] = true;
            for (let k = i + 1; k < m && board[k][j] === 'X'; k++) seen[k][j] = true;
        }
    }
    return count;
}

数组与矩阵专题的其他题目

查看数组与矩阵全部题目 →