class Solution {
    public int countBattleships(char[][] board) {
        int count = 0;
        int[][] visited = new int[board.length][board[0].length];
        for(int i=0; i<board.length; i++) { 
            for(int j=0; j<board[0].length; j++) { 
                if(board[i][j] == 'X') {
                    count = count + (countBattleshipsRec(board, j, i, visited) > 0 ? 1 : 0);
                }
            }
        }
        return count;
    }
    
    public int countBattleshipsRec(char[][] board, int x, int y, int[][] visited) {
        if(x<0 || x>=board[0].length)
            return 0;
        if(y<0 || y>=board.length)
            return 0;
        
        if(board[y][x] == '.') {
            return 0;
        }
        
        if(visited[y][x] == 1) {
            return 0;
        }
        
        visited[y][x] = 1;
        return 1 + countBattleshipsRec(board, x+1, y, visited) + countBattleshipsRec(board, x-1, y, visited) + countBattleshipsRec(board, x, y+1, visited) + countBattleshipsRec(board, x, y-1, visited);
    }
}