建站
咨詢
售后
建站咨詢
新聞中心
在其中尋找到所有只包含X（表示戰(zhàn)艦）或O（表示水）且沒有相鄰格子有其他字符的戰(zhàn)艦，我們可以使用一個二維數(shù)組來記錄每個位置是否已經(jīng)被訪問過。
作為一名程序員，我們時常需要解決各種有趣的問題。而LeetCode則是一個非常好的平臺，可以讓我們在編程中不斷挑戰(zhàn)自己。今天要介紹的題目是“數(shù)組419. 甲板上的戰(zhàn)艦”。
10年積累的成都網(wǎng)站制作、網(wǎng)站建設經(jīng)驗，可以快速應對客戶對網(wǎng)站的新想法和需求。提供各種問題對應的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡服務。我雖然不認識你，你也不認識我。但先網(wǎng)站設計后付款的網(wǎng)站建設流程，更有全州免費網(wǎng)站建設讓你可以放心的選擇與我們合作。
這道題目其實很簡單，但是卻能夠幫助我們加深對于數(shù)組和邏輯判斷等知識點之間關系的理解。
首先來看一下題目描述：
給定一個二維矩陣，在其中尋找到所有只包含X（表示戰(zhàn)艦）或O（表示水）且沒有相鄰格子有其他字符的戰(zhàn)艦，并返回其數(shù)量。
注意：相鄰格子指橫向或縱向連接在一起。
例如：
X..X
...X
以上面這個例子為例，我們可以發(fā)現(xiàn)其中存在兩艘長度分別為2和1的戰(zhàn)艦。而如果將它們轉化成0和1，則會變成以下形式：
1101
0011
從上面這個示意圖中可以看出來，原本連通區(qū)域內(nèi)部都被填充了數(shù)字1。而對于外邊界以及與其他聯(lián)通塊接觸處，則被標記為數(shù)字0。
根據(jù)這樣一個思路，在代碼實現(xiàn)中，我們可以使用一個二維數(shù)組來記錄每個位置是否已經(jīng)被訪問過。如果當前位置是X，并且它的上下左右都沒有其他字符，則表示這里存在一艘戰(zhàn)艦。
代碼實現(xiàn)如下：
```
class Solution {
public:
int countBattleships(vector
int m = board.size(), n = board[0].size();
vector
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') { // 如果當前位置未被訪問并且有戰(zhàn)艦
bool is_battle_ship = true;
// 檢查上下左右四個方向是否均為水或者未曾遍歷
if (i > 0 && board[i-1][j] == 'X' && visited[i-1][j]) is_battle_ship = false;
if (i< m - 1 && board[i+1][j] == 'X' && visited[i+1][j]) is_battle_ship = false;
if (j > 0 && board[i][j-1] == 'X' && visited[i][j-1]) is_battle_ship= false;
if (j< n - 1&&board[i][j+1]=='X'&&visited [i ][ j + l ])is_ battle _ship=false;
// 如果符合條件，就標記所有連通區(qū)域為已訪問，并將戰(zhàn)艦數(shù)+1
if (is_battle_ship) {
int x = i, y = j;
while (x >= 0 && board[x][j] == 'X' && !visited[x][j]) visited[x--][j] = true;
while (y >= 0 && board[i][y] == 'X' && !visited[i][y]) visited[i][y--] = true;
res++;
}
}
}
}
return res;
}
};
以上就是這道題目的解法。雖然看起來很簡單，但是在實現(xiàn)過程中也能夠鍛鍊我們對于數(shù)組和邏輯判斷等知識點之間關系的理解。
代碼練習不僅可以提高我們的編程技能，還能夠幫助我們加深對于各種算法問題的理解。因此，在平時學習中一定要多加練習，才能更好地掌握各種編程技巧。
最后，希望大家都可以成為優(yōu)秀的程序員！
名稱欄目：每日LeetCode：數(shù)組419.甲板上的戰(zhàn)艦
分享URL：http://fisionsoft.com.cn/article/djijejo.html
