当前位置：首页 > article >正文

代码随想录算法训练营第五十二天 | 图论part03

article 2025/2/26 22:10:46

                    
                        
                    
                    101. 孤岛的总面积 
#include <vector>
#include <iostream>

using namespace std;

int dir[4][2] = {0, 1, 0, -1, -1, 0, 1, 0};
void dfs(const vector<vector<int>> &grid, 
    vector<vector<bool>> &visited, int x, int y, int& result) {
        for (int i = 0; i < 4; ++i) {
            int nextx = x + dir[i][1];
            int nexty = y + dir[i][0];
            if (nextx < 0 || nextx >= grid.size()
            || nexty < 0 || nexty >= grid[0].size())  continue;
            if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {
                visited[nextx][nexty] = true;
                result++;
                dfs(grid, visited, nextx, nexty, result);
            }
        }
}

int main() {
    int n, m, result = 0;
    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));
    for (int j = 0; j < m; ++j) {
        if (grid[0][j] == 1 && visited[0][j] == false) {
                visited[0][j] = true;
                dfs(grid, visited, 0, j, result);
            }
        if (grid[n-1][j] == 1 && visited[n-1][j] == false) {
                visited[n-1][j] = true;
                dfs(grid, visited, n-1, j, result);
            }
    }
    
    for (int i = 0; i < n; ++i) {
        if (grid[i][0] == 1 && visited[i][0] == false) {
                visited[i][0] = true;
                dfs(grid, visited, i, 0, result);
            }
        if (grid[i][m-1] == 1 && visited[i][m-1] == false) {
                visited[i][m-1] = true;
                dfs(grid, visited, i, m-1, result);
            }
    }
    result = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 1 && visited[i][j] == false) {
                result++;
                visited[i][j] = true;
                dfs(grid, visited, i, j, result);
            }
        }
    }
    cout << result;
}
 
102. 沉没孤岛 
#include <vector>
#include <iostream>

using namespace std;

int dir[4][2] = {0, 1, 0, -1, -1, 0, 1, 0};
void dfs(vector<vector<int>> &grid, 
    vector<vector<bool>> &visited, int x, int y, bool transfer) {
        for (int i = 0; i < 4; ++i) {
            int nextx = x + dir[i][1];
            int nexty = y + dir[i][0];
            if (nextx < 0 || nextx >= grid.size()
            || nexty < 0 || nexty >= grid[0].size())  continue;
            if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {
                visited[nextx][nexty] = true;
                if (transfer) {
                    grid[nextx][nexty] = 0;
                }
                dfs(grid, visited, nextx, nexty, transfer);
            }
        }
}

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));
    for (int j = 0; j < m; ++j) {
        if (grid[0][j] == 1 && visited[0][j] == false) {
                visited[0][j] = true;
                dfs(grid, visited, 0, j, false);
            }
        if (grid[n-1][j] == 1 && visited[n-1][j] == false) {
                visited[n-1][j] = true;
                dfs(grid, visited, n-1, j, false);
            }
    }
    
    for (int i = 0; i < n; ++i) {
        if (grid[i][0] == 1 && visited[i][0] == false) {
                visited[i][0] = true;
                dfs(grid, visited, i, 0, false);
            }
        if (grid[i][m-1] == 1 && visited[i][m-1] == false) {
                visited[i][m-1] = true;
                dfs(grid, visited, i, m-1, false);
            }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 1 && visited[i][j] == false) {
                visited[i][j] = true;
                grid[i][j] = 0;
                dfs(grid, visited, i, j, true);
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << grid[i][j] << " ";
        }
        cout << endl;
    }
}
 
103. 水流问题 
#include <iostream>
#include <vector>

using namespace std;

int dir[4][2] = {0, 1, 0, -1, -1, 0, 1, 0};


void dfs(const vector<vector<int>> &grid, 
    vector<vector<bool>> &isVisited,int x, int y) {
    if (isVisited[x][y]) return;
    isVisited[x][y] = true;
    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 (grid[nextx][nexty] < grid[x][y])   continue;
        dfs(grid, isVisited,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>> Visited1(n, vector<bool>(m, false));
    vector<vector<bool>> Visited2(n, vector<bool>(m, false));
    for (int j = 0; j < m; ++j) {
        dfs(grid, Visited1, 0, j);
        dfs(grid, Visited2, n - 1, j);
    }
    for (int i = 0; i < n; ++i) {
        dfs(grid, Visited1, i, 0);
        dfs(grid, Visited2, i, m - 1);
    }
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (Visited1[i][j] && Visited2[i][j])
                cout << i << " " << j << endl;
        }
    }
}
 
104.建造最大岛屿 
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;

int dir[4][2] = {0, 1, 0, -1, -1, 0, 1, 0};
bool isAllGrid = true; 
void dfs(vector<vector<int>> &grid, vector<vector<bool>> &visited,
int &count, int mark, int x, int y) {
    if (visited[x][y] == true || grid[x][y] == 0) return;
    visited[x][y] = true;
    grid[x][y] = mark;
    count++;
    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;
        
        dfs(grid, visited, count, mark, nextx, nexty);
    }
}

void firstScan(vector<vector<int>> &grid, 
unordered_map<int, int> &gridNum, vector<vector<bool>> &visited) {
    int mark = 2;
    
    for (int i = 0; i < grid.size(); ++i) {
        for (int j = 0; j < grid[0].size(); ++j) {
            if (grid[i][j] == 0) isAllGrid = false;
            if (visited[i][j] == false && grid[i][j] == 1) {
                int count = 0;
                dfs(grid, visited, count, mark, i, j);
                gridNum.emplace(mark, count);
                mark++;
            }
        }
    }
}

int secondScan(vector<vector<int>> &grid, unordered_map<int, int> &gridNum) {
    int result = 0;
    unordered_set<int> visitedGrid;
    for (int i = 0; i < grid.size(); ++i) {
        for (int j = 0; j < grid[0].size(); ++j) {
            int count = 1;
            visitedGrid.clear(); //这里没有考虑到
            if (grid[i][j] == 0) {
                for (int a = 0; a < 4; ++a) {
                    int nextx = i + dir[a][0];
                    int nexty = j + dir[a][1];
                    if (nextx < 0 || nextx >= grid.size() || nexty < 0 
                    || nexty >= grid[0].size()) continue;
                    if (visitedGrid.count(grid[nextx][nexty])) continue;
                    
                    count += gridNum[grid[nextx][nexty]];
                    visitedGrid.insert(grid[nextx][nexty]);
                }
            }
            result = max(result, count);
        }
    }
    return result;
}

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];
        }
    }
    unordered_map<int, int> gridNum;
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    firstScan(grid, gridNum, visited);
    
    if (isAllGrid) {
        cout << n * m << endl; // 这个情况也没有考虑到
        return 0; 
    }
    cout << secondScan(grid, gridNum);
    return 0;
}

                