LeetCode 419. 甲板上的战舰（深度优先搜索dfs、数组）

419. 甲板上的战舰

思路：方法一，深度优先搜索dfs，遇到‘X’，就dfs一次，并在board中将其变为‘.’ 。

class Solution {
public:
    void dfs(int x,int y,vector<vector<char>>& board){
        if(board[x][y]!='X') return ;
        board[x][y]='.';
        if(x+1<board.size()) dfs(x+1,y,board);
        if(y+1<board[0].size()) dfs(x,y+1,board);
    }
    int countBattleships(vector<vector<char>>& board) {
        int ans=0;
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[i].size();j++){
                if(board[i][j]=='X'){
                    dfs(i,j,board);
                    ans++;
                }
            }
        }
        return ans;
    }
};

思路：方法二，进阶版，需要观察战舰的特点。如果遍历到战舰的头部，那么它的左边和上边都是没有‘X’的，如果是战舰的非头部部分，那么左边或上边会有‘X’，只需要找到这个特点，就可以统计出战舰的数量。

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