DFS/BFS 图论基础与海岛问题实战 (C/C++)

DFS/BFS 图论基础与海岛问题实战 (C/C++) | 极客日志

void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本节点相连的其他节点) {
        处理节点;
        dfs(图，选择的节点);
        // 回溯，撤销处理的结果
    }
}

#include <iostream>
#include <vector>
using namespace std;
const int N = 105;
int arr[N][N];
vector<int> cur;
vector<vector<int>> res;

void dfs(int k, int n) {
    if (k == n) {
        res.emplace_back(cur);
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (arr[k][i] == 1) {
            cur.emplace_back(i);
            dfs(i, n);
            cur.pop_back();
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        arr[x][y] = 1;
    }
    cur.emplace_back(1);
    dfs(1, n);
    if (res.size() == 0) {
        cout << -1 << endl;
    } else {
        for (auto vec : res) {
            for (int i = 0; i < vec.size() - 1; ++i) {
                cout << vec[i] << " ";
            }
            cout << vec[vec.size() - 1] << endl;
        }
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <list>
using namespace std;
const int N = 105;
vector<list<int>> graph(N);
vector<int> cur;
vector<vector<int>> res;

void dfs(int k, int n) {
    if (k == n) {
        res.emplace_back(cur);
        return;
    }
    for (int i : graph[k]) {
        cur.emplace_back(i);
        dfs(i, n);
        cur.pop_back();
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        graph[x].emplace_back(y);
    }
    cur.emplace_back(1);
    dfs(1, n);
    if (res.size() == 0) {
        cout << -1 << endl;
    } else {
        for (auto vec : res) {
            for (int i = 0; i < vec.size() - 1; ++i) {
                cout << vec[i] << " ";
            }
            cout << vec[vec.size() - 1] << endl;
        }
    }
    return 0;
}

// 定义四个方向的偏移量
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

void bfs(vector<vector<int>> grid, vector<vector<bool>> used) {
    queue<pair<int, int>> q;
    q.push({0, 0});
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        used[cur.first][cur.second] = true;
        for (int i = 0; i < 4; ++i) {
            int x = cur.first + dir[i][0];
            int y = cur.second + dir[i][1];
            if (x >= grid.size() || x < 0 || y >= grid[0].size() || y < 0)
                continue;
            if (!used[x][y]) {
                q.push({x, y});
            }
        }
    }
}

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 55;
int arr[N][N];
bool used[N][N];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

void dfs(int x, int y) {
    for (int i = 0; i < 4; ++i) {
        int x_cur = x + dir[i][0];
        int y_cur = y + dir[i][1];
        if (!used[x_cur][y_cur] && arr[x_cur][y_cur] == 1) {
            used[x_cur][y_cur] = true;
            dfs(x_cur, y_cur);
        }
    }
}

int main() {
    int n, m;
    int cnt = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> arr[i][j];
    memset(used, false, sizeof used);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (!used[i][j] && arr[i][j] == 1) {
                used[i][j] = true;
                cnt++;
                dfs(i, j);
            }
        }
    cout << cnt << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int result = 0;

void bfs(const vector<vector<int>> &grid, vector<vector<bool>> &used, int n, int m) {
    queue<pair<int, int>> que;
    que.push({n, m});
    used[n][m] = true;
    while (!que.empty()) {
        pair<int, int> cur = que.front();
        que.pop();
        for (int i = 0; i < 4; ++i) {
            int nextY = cur.first + dir[i][0];
            int nextX = cur.second + dir[i][1];
            if (nextX < 0 || nextX >= grid[0].size() || nextY < 0 || nextY >= grid.size())
                continue;
            if (grid[nextY][nextX] == 1 && !used[nextY][nextX]) {
                used[nextY][nextX] = true;
                que.push({nextY, nextX});
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    vector<vector<bool>> used(n, vector<bool>(m, false));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> grid[i][j];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 1 && !used[i][j]) {
                result++;
                bfs(grid, used, i, j);
            }
        }
    cout << result << endl;
    return 0;
}

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 55;
int arr[N][N];
bool used[N][N];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int cur_area;
int max_area;

void dfs(int x, int y) {
    for (int i = 0; i < 4; ++i) {
        int x_cur = x + dir[i][0];
        int y_cur = y + dir[i][1];
        if (!used[x_cur][y_cur] && arr[x_cur][y_cur] == 1) {
            used[x_cur][y_cur] = true;
            cur_area++;
            dfs(x_cur, y_cur);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> arr[i][j];
    memset(used, false, sizeof used);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (!used[i][j] && arr[i][j] == 1) {
                cur_area = 1;
                used[i][j] = true;
                dfs(i, j);
                max_area = max(max_area, cur_area);
            }
        }
    cout << max_area << endl;
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;
const int N = 55;
int arr[N][N];
bool used[N][N];
int n, m;
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

void dfs(int x, int y) {
    for (int i = 0; i < 4; ++i) {
        int cur_x = x + dir[i][0];
        int cur_y = y + dir[i][1];
        if (cur_x < 0 || cur_x >= m || cur_y < 0 || cur_y >= n)
            continue;
        if (used[cur_x][cur_y] || arr[cur_x][cur_y] == 0)
            continue;
        used[cur_x][cur_y] = true;
        dfs(cur_x, cur_y);
    }
}

int main() {
    cin >> m >> n;
    memset(used, false, sizeof used);
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            cin >> arr[i][j];
    // 清空边界
    for (int i = 0; i < m; ++i) {
        if (used[i][0] || arr[i][0] == 0) continue;
        used[i][0] = true;
        dfs(i, 0);
    }
    for (int i = 0; i < m; ++i) {
        if (used[i][n - 1] || arr[i][n - 1] == 0) continue;
        used[i][n - 1] = true;
        dfs(i, n - 1);
    }
    for (int i = 0; i < n; ++i) {
        if (used[0][i] || arr[0][i] == 0) continue;
        used[0][i] = true;
        dfs(0, i);
    }
    for (int i = 0; i < n; ++i) {
        if (used[m - 1][i] || arr[m - 1][i] == 0) continue;
        used[m - 1][i] = true;
        dfs(m - 1, i);
    }
    int cnt = 0;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (!used[i][j] && arr[i][j] == 1)
                cnt++;
    cout << cnt << endl;
    return 0;
}

#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>> &used, int x, int y) {
    used[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] == 1 && !used[nextX][nextY]) {
            used[nextX][nextY] = true;
            dfs(grid, used, 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>> used(n, vector<bool>(m, false));
    for (int i = 0; i < n; ++i) {
        if (grid[i][0] && !used[i][0]) dfs(grid, used, i, 0);
        if (grid[i][m - 1] && !used[i][m - 1]) dfs(grid, used, i, m - 1);
    }
    for (int i = 0; i < m; ++i) {
        if (grid[0][i] && !used[0][i]) dfs(grid, used, 0, i);
        if (grid[n - 1][i] && !used[n - 1][i]) dfs(grid, used, n - 1, i);
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] && used[i][j])
                cout << 1 << " ";
            else
                cout << 0 << " ";
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;
const int N = 105;
int n, m;
int arr[N][N];
int arr_one[N][N];
int arr_two[N][N];
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

void dfs(int cur_arr[N][N], int flag, int x, int y) {
    for (int i = 0; i < 4; ++i) {
        int cur_x = x + dir[i][0];
        int cur_y = y + dir[i][1];
        if (cur_x < 0 || cur_x >= n || cur_y < 0 || cur_y >= m)
            continue;
        if (cur_arr[cur_x][cur_y] != 0)
            continue;
        if (arr[x][y] <= arr[cur_x][cur_y]) {
            cur_arr[cur_x][cur_y] = flag;
            dfs(cur_arr, flag, cur_x, cur_y);
        }
    }
}

int main() {
    cin >> n >> m;
    memset(arr_one, 0, sizeof arr_one);
    memset(arr_two, 0, sizeof arr_two);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> arr[i][j];
    for (int i = 0; i < n; ++i) {
        arr_one[i][0] = 1;
        dfs(arr_one, 1, i, 0);
        arr_two[i][m - 1] = 2;
        dfs(arr_two, 2, i, m - 1);
    }
    for (int i = 0; i < m; ++i) {
        arr_one[0][i] = 1;
        dfs(arr_one, 1, 0, i);
        arr_two[n - 1][i] = 2;
        dfs(arr_two, 2, n - 1, i);
    }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (arr_one[i][j] == 1 && arr_two[i][j] == 2)
                cout << i << " " << j << endl;
    return 0;
}

#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;
const int N = 55;
int n, m;
int arr[N][N];
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

void dfs(int x, int y, int mark, int &cnt) {
    if (x < 0 || x >= n || y < 0 || y >= m)
        return;
    if (arr[x][y] != 1)
        return;
    cnt++;
    arr[x][y] = mark;
    for (int i = 0; i < 4; ++i) {
        dfs(x + dir[i][0], y + dir[i][1], mark, cnt);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> arr[i][j];
    int mark = 2;
    unordered_map<int, int> umap;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (arr[i][j] != 1)
                continue;
            int cnt = 0;
            dfs(i, j, mark, cnt);
            umap[mark++] = cnt;
        }
    }
    unordered_set<int> uset;
    int max_all = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (arr[i][j] != 0)
                continue;
            uset.clear();
            int all = 1;
            for (int k = 0; k < 4; ++k) {
                int x = i + dir[k][0];
                int y = j + dir[k][1];
                if (x < 0 || x >= n || y < 0 || y >= m)
                    continue;
                if (uset.find(arr[x][y]) != uset.end())
                    continue;
                all += umap[arr[x][y]];
                uset.insert(arr[x][y]);
            }
            max_all = max(max_all, all);
        }
    }
    if (max_all == 0)
        cout << umap[arr[0][0]] << endl;
    else
        cout << max_all << endl;
    return 0;
}

#include <iostream>
using namespace std;
const int N = 55;
int n, m;
int arr[N][N];
bool used[N][N];
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
int cnt = 0;

void dfs(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m) {
        cnt++;
        return;
    }
    if (used[x][y])
        return;
    if (arr[x][y] == 0) {
        cnt++;
        return;
    }
    used[x][y] = true;
    for (int i = 0; i < 4; ++i) {
        int cur_x = x + dir[i][0];
        int cur_y = y + dir[i][1];
        dfs(cur_x, cur_y);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> arr[i][j];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            if (arr[i][j] == 1) {
                dfs(i, j);
                cout << cnt << endl;
                return 0;
            }
        }
    return 0;
}

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;

unordered_map<string, int> umap;
unordered_set<string> uset;

bool get_cnt(string str1, string str2) {
    if (str1.size() != str2.size())
        return false;
    int cnt = 0;
    for (int i = 0; i < str1.size(); ++i) {
        if (str1[i] != str2[i])
            cnt++;
    }
    if (cnt != 1)
        return false;
    return true;
}

int main() {
    int n;
    string begin_str, end_str;
    cin >> n >> begin_str >> end_str;
    for (int i = 0; i < n; ++i) {
        string str;
        cin >> str;
        uset.insert(str);
    }
    queue<pair<string, int>> q;
    q.emplace(begin_str, 1);
    while (!q.empty()) {
        auto node = q.front();
        q.pop();
        string str = node.first;
        int cnt = node.second;
        if (get_cnt(str, end_str)) {
            cout << cnt + 1 << endl;
            return 0;
        }
        for (auto str_cur : uset) {
            if (umap.find(str_cur) != umap.end())
                continue;
            if (!get_cnt(str, str_cur))
                continue;
            umap.emplace(str_cur, cnt + 1);
            q.emplace(str_cur, cnt + 1);
        }
    }
    cout << 0 << endl;
    return 0;
}

#include <iostream>
#include <cstring>
#include <list>
#include <vector>
using namespace std;
const int N = 105;
int used[N];
vector<list<int>> graph(N);
int n, m;

void dfs(int i) {
    if (used[i] != 0)
        return;
    used[i] = 1;
    for (int node : graph[i])
        dfs(node);
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int s, t;
        cin >> s >> t;
        graph[s].push_back(t);
    }
    dfs(1);
    for (int i = 1; i <= n; ++i)
        if (used[i] == 0) {
            cout << -1 << endl;
            return 0;
        }
    cout << 1 << endl;
    return 0;
}

DFS/BFS 图论基础与海岛问题实战 (C/C++)

图论基础理论

DFS 与 BFS 的区别

DFS（深度优先搜索）

DFS 模版

例题：所有可达路径

利用邻接矩阵进行深搜

利用邻接表进行深搜

BFS（广度优先搜索）

岛屿问题实战

1、岛屿数量（dfs）

DFS 解法

BFS 解法

2、岛屿的面积（dfs）

3、孤岛的总面积（dfs）

4、沉没孤岛（dfs）

5、水流问题

6、建造最大岛屿

7、岛屿的周长

8、字符串接龙

9、有向图的完全联通

参考资料

更多推荐文章

相关免费在线工具

DFS/BFS 图论基础与海岛问题实战 (C/C++)

图论基础理论

DFS 与 BFS 的区别

DFS（深度优先搜索）

DFS 模版

例题：所有可达路径

利用邻接矩阵进行深搜

利用邻接表进行深搜

BFS（广度优先搜索）

岛屿问题实战

1、岛屿数量（dfs）

DFS 解法

BFS 解法

2、岛屿的面积（dfs）

3、孤岛的总面积（dfs）

4、沉没孤岛（dfs）

5、水流问题

6、建造最大岛屿

7、岛屿的周长

8、字符串接龙

9、有向图的完全联通

参考资料

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具