99. 岛屿の数 - 深度優先探査

リンク: 99. 岛屿の数 - 深度優先探査

方針: 未 visit した陆上に遭遇した場合、+1 し、その陆と接する他の陆も visit marking します。

# include <iostream>
# include <vector>
# using namespace std;

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四つの方向
void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 超出了境界
        if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 未 visit した 陆上的
            visited[nextx][nexty] = true;
            dfs(grid, visited, nextx, nexty);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    vector<vector<bool>> visited(n, vector<bool>(m, false));

    int result = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j] && grid[i][j] == 1) {
                visited[i][j] = true;
                result++;
                dfs(grid, visited, i, j);
            }
        }
    }

    cout << result << endl;
}

99. 岛屿の数 - 幾何学的探査

リンク: 99. 岛屿の数 - 幾何学的探査

方針: 陆上に遭遇した場合、+1 し、その陆と接する他の陆も visit marking します。

# include <iostream>
# include <vector>
# include <queue>
# using namespace std;

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四つの方向
void bfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
    queue<pair<int, int>> que;
    que.push({x, y});
    visited[x][y] = true;
    while(!que.empty()) {
        pair<int, int> cur = que.front(); que.pop();
        int curx = cur.first;
        int cury = cur.second;
        for (int i = 0; i < 4; i++) {
            int nextx = curx + dir[i][0];
            int nexty = cury + dir[i][1];
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 超出了境界
            if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {
                que.push({nextx, nexty});
                visited[nextx][nexty] = true;
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    vector<vector<bool>> visited(n, vector<bool>(m, false));

    int result = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j] && grid[i][j] == 1) {
                result++;
                bfs(grid, visited, i, j);
            }
        }
    }

    cout << result << endl;
}

100. 岛屿の最大面積

リンク: 100. 岛屿の最大面積

方針: 前の 2 問題と似ているが、面積を数え、最大面積を保管します。

# include <iostream>
# include <vector>
# using namespace std;
int count;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四つの方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 超出了境界
        if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 未 visit した 陆上的
            visited[nextx][nexty] = true;
            count++;
            dfs(grid, visited, nextx, nexty);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    vector<vector<bool>> visited(n, vector<bool>(m, false));
    int result = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j] && grid[i][j] == 1) {
                count = 1;  // 初期化: 適当な陆上に遭遇した場合、+1 する
                visited[i][j] = true;
                dfs(grid, visited, i, j);
                result = max(result, count);
            }
        }
    }

    cout << result << endl;
}