clueless coding // TODO: be smarter

LeetCode 419. Battleships in a Board: Java Solution



Problem Statement


Given an 2D board, count the total number of battleships on it. Battleships are represented by ‘X’s, and empty board slots are represented by ‘.’s. You can assume the following information:

You receive a valid board - every spot is either an empty space or contains a battleship.

Battleships are placed horizontally or vertically.

No two battleships are ‘touching’ - every battleship has a least on space of separation between them. You will have no adjacent ‘X’s that do not belong to the same battleship.

Function Signature (Java):
  int countBattleships(char[][] board)

Inputs:
X..X.X
...X.X
...X..

Outputs:
  3

Inputs:
.X..
XXXX
.X..

Invalid board - adjacent battleships.



TL;DR Code Solution



public void dfs(char[][]board, int i, int j) {

    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'X') {
        return;
    }
    board[i][j] = 'x';

    dfs(board, i+1, j);
    dfs(board, i-1, j);
    dfs(board, i, j+1);
    dfs(board, i, j-1);

}

public int countBattleships(char[][] board) {

    int result = 0;

    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (board[i][j] == 'X') {
                result += 1;
                dfs(board, i, j);
            }    
        }
    }

    return result;

}