# O(N*M) memory and without changing the board. This works when received the invalid board also.

• This code will take the invalid boards and the code will not modify the board. But it will take O(n * m) space for visited array to track the visited nodes and also O(n * m) space in worst case for dfs if the entire board is filled with 'X'. Time complexity is also O(n * m). Here 'n' is the number of rows and 'm' is the number cells in each row.

``````public://O(N*M) memory and without changing the board. This works when received the invalid board also.
int countBattleships(vector<vector<char>>& board) {
int nr = board.size();
if (!nr) return 0;
int nc = board[0].size();
vector<vector<char>>visited = board;
int count = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
visited[r][c] = '0';//not visited
}
}
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (board[r][c] == '.') {
visited[r][c] = '1';
continue;
}
if (board[r][c] == 'X' && visited[r][c] == '0') {
bool res = true;
visited[r][c] = '1';
dfs(board, r, c, res, visited);
if (res)
count++;
}
}
}
return count;
}
private:
void dfs(vector<vector<char>>&board, int r, int c, bool &res, vector<vector<char>>&visited) {
if (valid(r + 1, c + 1, board) && board[r][c + 1] == 'X' && board[r + 1][c] == 'X' ||
valid(r + 1, c - 1, board) && board[r + 1][c] == 'X' && board[r][c - 1] == 'X' ||
valid(r - 1,c + 1, board) && board[r - 1][c] == 'X' && board[r][c + 1] == 'X' ||
valid(r - 1,c - 1, board) && board[r-1][c] == 'X' && board[r][c-1] == 'X')
res = false;
if (valid(r - 1, c, board ) && board[r - 1][c] == 'X' && visited[r - 1][c] != '1') { visited[r - 1][c] = '1'; dfs(board, r - 1, c, res, visited); }
if (valid(r + 1, c, board) && board[r + 1][c] == 'X' && visited[r + 1][c] != '1') { visited[r + 1][c] = '1'; dfs(board, r + 1, c, res, visited);  }
if (valid(r, c - 1, board) && board[r][c - 1] == 'X' && visited[r][c -1 ] != '1') { visited[r][c - 1] = '1'; dfs(board, r, c - 1, res, visited);  }
if (valid(r, c + 1, board) && board[r][c + 1] == 'X' && visited[r][c + 1] != '1') { visited[r][c + 1] = '1'; dfs(board, r, c + 1, res, visited); }
}
bool valid(int r, int c, vector<vector<char>>&board) {
return (r >= 0 && r < board.size() && c >= 0 && c < board[0].size());
}
``````

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