leetcode 419. Battleships in a Board | 419. 甲板上的战舰（二维矩阵DFS经典“感染”思路）

矫情吗；* 2022-09-03 04:15 100阅读 0赞

## 题目 ##

[https://leetcode.com/problems/battleships-in-a-board/][https_leetcode.com_problems_battleships-in-a-board]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

一道简单的 medium 题，仍然是“感染”的思想，只不过本题“感染”的过程是消除的过程。

class Solution { 
        int M;
        int N;
        int count;
    
        public int countBattleships(char[][] board) { 
            M = board.length;
            N = board[0].length;
            count = 0;
            for (int i = 0; i < M; i++) { 
                for (int j = 0; j < N; j++) { 
                    if (board[i][j] == 'X') { 
                        count++;
                        bfsErase(board, i, j);
                    }
                }
            }
            return count;
        }
    
        public void bfsErase(char[][] board, int i, int j) { 
            if (i < 0 || j < 0 || i >= M || j >= N) return;
    
            board[i][j] = '.';
            if (i > 0 && board[i - 1][j] == 'X') { 
                bfsErase(board, i, j);
            } else if (j > 0 && board[i][j - 1] == 'X') { 
                bfsErase(board, i, j - 1);
            } else if (i < M - 1 && board[i + 1][j] == 'X') { 
                bfsErase(board, i + 1, j);
            } else if (j < N - 1 && board[i][j + 1] == 'X') { 
                bfsErase(board, i, j + 1);
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

[https_leetcode.com_problems_battleships-in-a-board]: https://leetcode.com/problems/battleships-in-a-board/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/06f6a06150c94e2d8c44544bebcd5d75.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/fdb61708e0484a9b9c94564da30dfa5d.png