今天的題目是計算有幾個小島 200. Number of Islands:題目給定一個二維陣列,1 : 陸地、0 : 海洋,水平垂直有連接的就是一座島嶼,以下面測資為例就是三個小島。
Input: 11000 11000 00100 00011 Output: 3
地圖遍尋的題目看來就是需要 DFS/BFS 出馬解決。我們另外準備一個陣列紀錄是否拜訪過,程式開始一一遍尋每個點,如果曾經拜訪或是海洋就跳過,不然就 DFS/BFS 把相鄰的都跑一遍,最後就可以算出有幾個小島了。
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if(grid.empty() || grid[0].empty()) return 0;
vector<vector<bool>> visit(grid.size(), vector<bool>(grid[0].size()));
int res = 0;
for(int i=0; i<grid.size(); i++){
for(int j=0; j<grid[i].size(); j++){
if(grid[i][j] == '0' || visit[i][j] == 1) continue;
checkIsland(grid, visit, i, j);
res++;
}
}
return res;
}
void checkIsland(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == '0' || visited[x][y]) return;
visited[x][y] = true;
checkIsland(grid, visited, x - 1, y);
checkIsland(grid, visited, x + 1, y);
checkIsland(grid, visited, x, y - 1);
checkIsland(grid, visited, x, y + 1);
}