每日一题:419. 甲板上的战舰

解题思路

类似于岛屿数量问题,只需要在图中找出练成一片的X即可

代码

class Solution {
    int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
    public int countBattleships(char[][] board) {
        int res = 0;
        for (int i=0;i<board.length;i++){
            for (int j=0;j<board[i].length;j++){
                if (board[i][j] == 'X'){
                    res++;
                    dfs(i,j,board);
                }
            }
        }
        return res;
    }
    public void dfs(int x,int y,char[][] board){
        board[x][y] = '.';
        for (int i=0;i<dir.length;i++){
            if (x+dir[i][0]>=0 && dir[i][0]+x<board.length && y+dir[i][1]>=0 && y+dir[i][1]<board[0].length && board[x+dir[i][0]][y+dir[i][1]]=='X'){
                dfs(x+dir[i][0],y+dir[i][1],board);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23