419.甲板上的战舰(dfs, 沉没战舰)

    科技2025-04-13  43

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

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

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

    无效样例 :

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

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/battleships-in-a-board 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


    思考

    我们打算遍历这个二维数组,然后遇到X就开始就记个数。但这样有个问题,比如又变那一列,3个X其实是一艘战舰,如果遇上了都数一遍,就会重复数。

    所以数过的战舰需要“沉没”掉,把"X"变为"."

    怎样探索一艘战舰包含哪些X呢,注意到战舰只能横向或者纵向成一竖。

    首先检查点有没有越界,是不是在甲板上(X),不是的话直接返回。

    符合条件的话:

    我们就先将这个点变成".",然后对这个点进行深度优先搜索,向四周探索。

    探索到下一个X点,就继续dfs.

    下图注释

    遍历二维数组,到(0,0),发现是X。船数+1

    就dfs(0,0)

        将board[0][0] = "."

        然后dfs四周的点。发现左边和上边的点越界了,右边和下边的点不是X,所以直接返回。

     

    然后遍历(0,1),  (0,2), 都不是X,没事

     

    到(0,3)了,它是X,船数+1. dfs(0,3)

     首先将board[0][3]置为"."

    dfs四周的点。

    左边不是X,上和右边越界了,直接返回。

    dfs(1,3)

    没有越界,且是X

    board[1][3] 置为"."

    dfs四周

    这个时候,左边上边都不是X,右边越界,直接返回。

     

    dfs(2,3)

    没有越界,且是X

    board[2][3] 置为"."

    左边,上边都不是X,下边和右边越界,直接返回。

     

    回到主遍历线,遍历(1,0), (1,1)......     (2,3),都没找到X,所以返回战舰数2


    代码实现 

    /** * @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] !== 'X') { return } //沉默当前点 board[row][col] = '.' //对四个方向进行深度优先搜索 dfs(row-1, col) dfs(row+1, col) dfs(row, col-1) dfs(row, col+1) } return result };

     

    Processed: 0.070, SQL: 8