Loading... > https://leetcode.cn/problems/battleships-in-a-board/description/?envType=daily-question&envId=2024-05-02 因为没有连着的战舰，所以可以直接对每个点向右和向下进行搜索，并把搜索过的路径标记为已搜索，最终进行了几次搜索就有几艘战舰。 ```c++ class Solution { public: int countBattleships(std::vector<std::vector<char>>& board) { const int m = board.size(), n = board[0].size(); bool visited[m][n]; memset(visited, 0, sizeof(visited)); int res = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (visited[i][j] || board[i][j] != 'X') continue; visited[i][j] = true; if (i + 1 < m && board[i + 1][j] == 'X') { for (int k = i + 1; k < m && board[k][j] == 'X'; k++) visited[k][j] = true; } else if (j + 1 < n && board[i][j + 1] == 'X') { for (int k = j + 1; k < n && board[i][k] == 'X'; k++) visited[i][k] = true; } res++; } } return res; } }; ``` - 时间复杂度：$O(m \times n)$ ，其中 $m, n$ 为 `board` 的行列数。 - 空间复杂度：$O(m \times n)$ 。 ### 进阶 进阶要求一次扫描，只使用 $O(1)$ 的空间，且不修改 `board` 中的值。因为没有连着的战舰，所以每艘战舰的左上角的点，它的左边和上面一定是空的。因此我们可以遍历每个点，如果该点为战舰标记且其左边和上面为空或者不存在，则战舰数加一。 ```c++ class Solution { public: int countBattleships(std::vector<std::vector<char>>& board) { const int m = board.size(), n = board[0].size(); int res = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] != 'X') continue; if (i > 0 && board[i - 1][j] == 'X') continue; if (j > 0 && board[i][j - 1] == 'X') continue; res++; } } return res; } }; ``` - 时间复杂度：$O(m \times n)$ ，其中 $m, n$ 为 `board` 的行列数。 - 空间复杂度：$O(1)$ 。 最后修改：2024 年 06 月 12 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏