---
tags: leetcode
---

# [419. Battleships in a Board](https://leetcode.com/problems/battleships-in-a-board/)
---
# My Solution
## Solution 1: DFS
### The Key Idea for Solving This Coding Question
### C++ Code

#define WHITE (0)  // not visited
#define GRAY  (1)  // visiting this node or its descendants
#define BLACK (2)  // have visited this node and all its descendants.

#define SHIP  ('X')
#define EMPTY ('.')

class Solution {
public:
    int countBattleships(vector<vector<char>> &board) {
        rows = board.size();
        cols = board[0].size();

        vector<vector<int>> state(rows, vector<int>(cols, WHITE));
        int numOfShips = 0;

        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (state[r][c] == WHITE && board[r][c] == SHIP) {
                    dfs(board, state, r, c);
                    ++numOfShips;
                }
            }
        }

        return numOfShips;
    }

private:
    int rows;
    int cols;

    void dfs(vector<vector<char>> &board, vector<vector<int>> &state, int r, int c) {
        vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        state[r][c] = GRAY;

        for (auto &dir : dirs) {
            int nextR = r + dir[0], nextC = c + dir[1];
            if (nextR < 0 || rows <= nextR || nextC < 0 || cols <= nextC ||
                state[nextR][nextC] != WHITE || board[nextR][nextC] != SHIP) {
                continue;
            }
            dfs(board, state, nextR, nextC);
        }

        state[r][c] = BLACK;
    }
};

### Time Complexity
$O(mn)$
* $m$ is the number of rows of `board`.
* $n$ is the number of columns of `board`.
### Space Complexity
$O(mn)$
* $m$ is the number of rows of `board`.
* $n$ is the number of columns of `board`.
## Solution 2: BFS
### The Key Idea for Solving This Coding Question
### C++ Code

struct cell {
    int r; 
    int c;
    cell(int r, int c) : r(r), c(c) {} 
};
	
#define WHITE (0) // not visited
#define GRAY  (1) // visiting this node and its neighbors
#define BLACK (2) // has visited this node and all its neighbors.

#define SHIP ('X')
#define EMPTY ('.')

class Solution {
public:
    int countBattleships(vector<vector<char>> &board) {
        rows = board.size();
        cols = board[0].size();

        vector<vector<int>> state(rows, vector<int>(cols, WHITE));
        int numOfShips = 0;

        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (state[r][c] == WHITE  && board[r][c] == SHIP) {
                    bfs(board, state, r, c);
                    ++numOfShips;
                }
            }
        }

        return numOfShips;
    }

private:
    int rows;
    int cols;

    void bfs(vector<vector<char>> &board, vector<vector<int>> &state, int r, int c) {
        vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        queue<cell> q;

        q.push(cell(r, c));
        state[r][c] = GRAY;
        while (!q.empty()) {
            cell curr = q.front();
            q.pop();

            for (auto &dir : dirs) {
                int nextR = curr.r + dir[0], nextC = curr.c + dir[1];
                if (nextR < 0 || rows <= nextR || nextC < 0 || cols <= nextC ||
                    state[nextR][nextC] != WHITE || board[nextR][nextC] != SHIP) {
                    continue;
                }
                q.push(cell(nextR, nextC));
                state[nextR][nextC] = GRAY;
            }
            state[curr.r][curr.c] = BLACK;
        }
    }
};

### Time Complexity
$O(mn)$
* $m$ is the number of rows of `board`.
* $n$ is the number of columns of `board`.
### Space Complexity
$O(mn)$
* $m$ is the number of rows of `board`.
* $n$ is the number of columns of `board`.