推 jensheng09: 你到底有沒有拍裸照給阿消 04/19 16:26
推 JIWP: 大師 教我 04/19 16:28
推 sustainer123: 大師 救我 04/19 16:30
→ oinishere: 你們兩個韌體600萬 咕咕嚕外商 在這裡跟大一的叫甚麼 04/19 16:31
推 DJYOSHITAKA: 別捲了 04/19 16:38
推 SecondRun: 大師 教我 04/19 16:53
※ 引述 《sustainer123 (caster)》 之銘言：
:
: ※ 引述《Rushia (早瀬ユウカの体操服 )》之銘言：
: : https://leetcode.com/problems/number-of-islands/description
: : 200. Number of Islands
: : 給你一個二維陣列 1 表示陸地 0 表示海水，相連的陸地是一的島嶼，求出有幾個島。
: : 思路：
: : 1.找到 grid[i][j] == 1 的格子就把島嶼數量+1，並以該點為中心 dfs 附近相鄰的陸
地
: : 標記為已經走過。
: : 2.返回島嶼數量。
到處走 到處改成0
cpp的code寫起來感覺蠻整齊的欸
class Solution {
public:
int island;
void walk(vector<vector<char>>& grid , int i , int j)
{
grid[i][j] = '0';
if(i>0)
{
if(grid[i-1][j] == '1')
{
walk(grid , i-1 , j);
}
}
if(j>0)
{
if(grid[i][j-1] == '1')
{
walk(grid , i , j-1);
}
}
if(i<grid.size()-1)
{
if(grid[i+1][j] == '1')
{
walk(grid , i+1 , j);
}
}
if(j<grid[0].size()-1)
{
if(grid[i][j+1] == '1')
{
walk(grid , i , j+1);
}
}
}
int numIslands(vector<vector<char>>& grid)
{
island = 0;
for(int a = 0 ; a < grid.size() ; a ++)
{
for(int b = 0 ; b < grid[0].size() ; b ++)
{
if(grid[a][b] == '1')
{
island++;
walk(grid,a,b);
}
}
}
return island;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.138.244 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1713515180.A.E74.html