# 419. Battleships in a Board

Given an 2D board, count how many battleships are in it. The battleships are represented with `'X'`s, empty slots are represented with `'.'`s. You may assume the following rules:

• You receive a valid board, made of only battleships or empty slots.
• Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape `1xN` (1 row, N columns) or `Nx1` (N rows, 1 column), where N can be of any size.
• At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.

Example:

``````X..X
...X
...X
``````

In the above board there are 2 battleships.

Invalid Example:

``````...X
XXXX
...X
``````

This is an invalid board that you will not receive - as battleships will always have a cell separating between them.

Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?

``````class Solution {
public:
int countBattleships(vector<vector<char>>& board) {
if (board.empty() || board[0].empty()) return 0;
int res = 0, m = board.size(), n = board[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == '.' || (i > 0 && board[i - 1][j] == 'X') || (j > 0 && board[i][j - 1] == 'X')) continue;
++res;
}
}
return res;
}
};
``````

``````class Solution {
public:
int countBattleships(vector<vector<char>>& board) {
if (board.empty() || board[0].empty()) return 0;
int m = board.size(), n = board[0].size(), res = 0;
vector<vector<bool>> visited(m, vector<bool>(n, false));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 'X' && !visited[i][j]) {
int vertical = 0, horizontal = 0;
dfs(board, visited, vertical, horizontal, i, j);
if (vertical == i || horizontal == j) ++res;
}
}
}
return res;
}
void dfs(vector<vector<char>>& board, vector<vector<bool>>& visited, int& vertical, int& horizontal, int i, int j) {
int m = board.size(), n = board[0].size();
if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || board[i][j] == '.') return;
vertical |= i; horizontal |= j;
visited[i][j] = true;
dfs(board, visited, vertical, horizontal, i - 1, j);
dfs(board, visited, vertical, horizontal, i + 1, j);
dfs(board, visited, vertical, horizontal, i, j - 1);
dfs(board, visited, vertical, horizontal, i, j + 1);
}
};
``````

``````class Solution {
public:
int countBattleships(vector<vector<char>>& board) {
if (board.empty() || board[0].empty()) return 0;
int res = 0, m = board.size(), n = board[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
vector<vector<int>> dirs{{0,-1},{-1,0},{0,1},{1,0}};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 'X' && !visited[i][j]) {
++res;
queue<pair<int, int>> q;
q.push({i, j});
while (!q.empty()) {
auto t = q.front(); q.pop();
visited[t.first][t.second] = true;
for (auto dir : dirs) {
int x = t.first + dir[0], y = t.second + dir[1];
if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y] || board[x][y] == '.') continue;
q.push({x, y});
}
}
}
}
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/419

https://leetcode.com/problems/battleships-in-a-board/

https://leetcode.com/problems/battleships-in-a-board/discuss/90902/Simple-Java-Solution

https://leetcode.com/problems/battleships-in-a-board/discuss/90957/dfs-bfs-flood-fill-algorithm-with-c

https://leetcode.com/problems/battleships-in-a-board/discuss/90913/Share-my-7-line-code-1-line-core-code-3ms-super-easy

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation