C++LeetCode 구현(200.섬의 수)

[LeetCode]200.Number of Islands 섬의 수
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3
이 섬 수량 을 구 하 는 문 제 는 본질 적 으로 행렬 의 연속 구역 의 개 수 를 구 하 는 것 이다.DFS 를 깊이 있 게 검색 하여 풀 어야 한 다 는 것 을 쉽게 생각 할 수 있다.우 리 는 visited 배열 을 만들어 서 특정한 위치 가 방문 되 었 는 지,'1'이 고 방문 되 지 않 은 위치 에 대해 상하 좌우 위치 에'1'인 수 를 기록 해 야 한다.visited 대응 값 을 true 로 부여 하고 연 결 된 모든 인접 위치 에 계속 들 어 갑 니 다.그러면 이 연결 구역 의 모든 수 를 찾 을 수 있 습 니 다.그리고 해당 하 는 visited 중의 값 을 true 로 부여 합 니 다.인접 지역 을 찾 은 후에 결 과 를 res 를 1 로 증가 시 킨 다음 에'1'이 고 방문 되 지 않 은 위 치 를 계속 찾 을 수 있 습 니 다.이 를 통 해 전체 원 배열 을 옮 겨 다 닐 때 까지 최종 결 과 를 얻 을 수 있 습 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int m = grid.size(), n = grid[0].size(), res = 0;
        vector<vector<bool>> visited(m, vector<bool>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '0' || visited[i][j]) continue;
                helper(grid, visited, i, j);
                ++res;
            }
        }
        return res;
    }
    void helper(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;
        helper(grid, visited, x - 1, y);
        helper(grid, visited, x + 1, y);
        helper(grid, visited, x, y - 1);
        helper(grid, visited, x, y + 1);
    }
};

물론 이런 미로 같은 제목 DFS 와 BFS 두 쌍 의 친 한 친구 들 은 그림자 처럼 붙 어 다 닐 것 이다.그러면 BFS 가 시작 할 것 이다.사실은 간단 합 니 다.'1'에 옮 겨 다 닐 때 이 위치 에 방문 한 적 이 없 으 면 BFS 를 호출 하면 됩 니 다.대기 열 quue 를 통 해 이 루어 집 니 다.현재 위 치 를 대기 열 에 추가 한 다음 에 while 순환 을 하여 팀 의 첫 번 째 요 소 를 추출 하고 주변 네 개의 위 치 를 옮 겨 다 니 며 경 계 를 넘 지 않 았 다 면...visited 에 있 는 이 이웃 의 위 치 를 true 로 표시 하고 다음 에 옮 겨 다 니 기 를 기다 리 면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int m = grid.size(), n = grid[0].size(), res = 0;
        vector<vector<bool>> visited(m, vector<bool>(n));
        vector<int> dirX{-1, 0, 1, 0}, dirY{0, 1, 0, -1};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '0' || visited[i][j]) continue;
                ++res;
                queue<int> q{{i * n + j}};
                while (!q.empty()) {
                    int t = q.front(); q.pop();
                    for (int k = 0; k < 4; ++k) {
                        int x = t / n + dirX[k], y = t % n + dirY[k];
                        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '0' || visited[x][y]) continue;
                        visited[x][y] = true;
                        q.push(x * n + y);
                    }
                }
            }
        }
        return res;
    }
};

Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/200
유사 한 제목:
Number of Islands II
Surrounded Regions
Walls and Gates
Number of Connected Components in an Undirected Graph  
Number of Distinct Islands  
Max Area of Island
참고 자료:
https://leetcode.com/problems/number-of-islands/
https://leetcode.com/problems/number-of-islands/discuss/56589/C%2B%2B-BFSDFS
https://leetcode.com/problems/number-of-islands/discuss/56359/Very-concise-Java-AC-solution
C++실현 LeetCode(200.섬의 수)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++실현 섬의 수 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!