419. 甲板上的战舰

image.png

这个题基本思路和岛屿的数量问题是一致，需要注意的是
题目已经说了：两条战舰不能直接相邻，必须有“.”来隔开
所以这样就不可以

image.png

和岛屿的代码都一样

class Solution {
    public int countBattleships(char[][] board) {
       //if(board.length==0) return 0;
       int count=0;
       for(int i=0;i<=board.length-1;i++){
           for(int j=0;j<=board[0].length-1;j++){
               if(board[i][j]=='X'){
                   count++;
                   dfs(i,j,board);
                   
               }
           }
       }
       return count;
    }
     void dfs(int i,int j,char[][] board){
        if(i<0||i>=board.length||j<0||j>=board[0].length||board[i][j]!='X') return;
        board[i][j]='.';//沉没
        dfs(i-1,j,board);
        dfs(i+1,j,board);
        dfs(i,j-1,board);
        dfs(i,j+1,board);
    }
}

image.png

进阶版，要求不修改甲板值，就是指不能去沉没
这样可以用判断来解决，如果当前点是X，如果该点的前一个点和左边的点是X，那说明这个点就不能++，之前已经统计过了

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