1. 題目

給定一個二維的甲板， 請計算其中有多少艘戰艦。
戰艦用 'X'表示，空位用 '.'表示。 你需要遵守以下規則：

給你一個有效的甲板，僅由戰艦或者空位組成。

戰艦只能水平或者垂直放置。
換句話說, 戰艦只能由 1xN (1 行, N 列)組成，或者 Nx1 (N 行, 1 列)組成，其中N可以是任意大小。
兩艘戰艦之間至少有一個水平或垂直的空位分隔 - 即沒有相鄰的戰艦。

示例 : X..X ...X ...X 在上面的甲板中有2艘戰艦。無效樣例 :...X XXXX ...X 你不會收到這樣的無效甲板 - 因為戰艦之間至少會有一個空位將它們分開。 進階: 你可以用一次掃描算法，只使用 O(1)額外空間，并且不修改甲板的值來解決這個問題嗎？

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/battleships-in-a-board
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

class Solution { public:int countBattleships(vector<vector<char>>& board) {int m = board.size(), n = board[0].size();int i, j, sum = 0;for(i = 0; i < m; ++i)for(j = 0; j < n; ++j){if(board[i][j] == 'X'){sum += 1;if((i-1>=0 && board[i-1][j]=='X') || (j-1>=0 && board[i][j-1]=='X'))sum -= 1;//上面有或者左邊有都是連著的，不能算}}return sum;} };

12 ms 9.6 MB

總結

以上是生活随笔為你收集整理的LeetCode 419. 甲板上的战舰的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。