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