✅419. 甲板上的战舰

[bazinga-web]

419. 甲板上的战舰

给定一个二维的甲板， 请计算其中有多少艘战舰。 战舰用 'X'表示，空位用 '.'表示。 你需要遵守以下规则：

给你一个有效的甲板，仅由战舰或者空位组成。
战舰只能水平或者垂直放置。换句话说,战舰只能由 1xN (1 行, N 列)组成，或者 Nx1 (N 行, 1 列)组成，其中N可以是任意大小。
两艘战舰之间至少有一个水平或垂直的空位分隔 - 即没有相邻的战舰。
示例 :

X..X
...X
...X
在上面的甲板中有2艘战舰。

无效样例 :

...X
XXXX
...X
你不会收到这样的无效甲板 - 因为战舰之间至少会有一个空位将它们分开。

进阶:

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

[bazinga-web]

解题思路同200题岛屿的数量相同，都是采用沉没法

/**
 * @param {character[][]} board
 * @return {number}
 */
var countBattleships = function(board) {
    let result = 0;
    for (let row = 0; row < board.length; row++) {
        for (let col = 0; col < board[0].length; col++) {
            if (board[row][col] === 'X') {
                result++;
                dfs(row, col);
            }
        }
    }

    function dfs(row, col) {
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] === '.') return;
        board[row][col] = '.';
        dfs(row-1, col);
        dfs(row+1, col);
        dfs(row, col-1);
        dfs(row, col+1);
    }

    return result;
};

[Ray-56]

此题与200. 岛屿数量一致

/**
 * @param {character[][]} board
 * @return {number}
 */
var countBattleships = function(board) {
	const xLen = board.length;
	const yLen = board[0].length;
	let ret = 0;
	for (let x = 0; x < xLen; x++) {
		for (let y = 0; y < yLen; y++) {
			if (board[x][y] === 'X') {
				ret++;
				h(board, x, y, xLen, yLen);
			}
		}
	}
	return ret;
};
function h(board, x, y, xLen, yLen) {
	if (x < 0 || y < 0 || x >= xLen || y >= yLen || board[x][y] === '.') return;
	board[x][y] = '.';
	h(board, x - 1, y, xLen, yLen);
	h(board, x + 1, y, xLen, yLen);
	h(board, x, y - 1, xLen, yLen);
	h(board, x, y + 1, xLen, yLen);
}