I want to know if there is any solution without auxiliary array


  • 0
    L
    public int countBattleships(char[][] board) {
        int count = 0;
        int N = board.length;
        int M = board[0].length;
        boolean[][] marked = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!marked[i][j] && board[i][j] == 'X'){
                    int tmpi = i, tmpj = j;
                    while (tmpi < N && board[tmpi][j] == 'X') marked[tmpi++][j] = true;
                    while (tmpj < M && board[i][tmpj] == 'X') marked[i][tmpj++] = true;
                    count++;
                }
            }
        }
        return count;
    }

  • 0
    G

    Yes. Just count the top left of each battleship. That's enough. Also remember it says no two ships are adjacent.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.