// 定义四个方向的偏移量int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
voidbfs(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 >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && !used[x][y]) {
q.push({x, y});
}
}
}
}
经典岛屿问题系列
想要学好图论,必须熟练运用 DFS 与 BFS。下面通过九道经典'岛屿问题'来磨炼基本式。
1. 岛屿数量
给定由 1(陆地)和 0(水)组成的矩阵,计算岛屿数量。相邻的陆地算作同一岛屿。
DFS 解法:
#include<iostream>#include<cstring>#include<vector>usingnamespace std;
constint N = 55;
int arr[N][N];
bool used[N][N];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
voiddfs(int x, int y){
for (int i = 0; i < 4; ++i) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx >= 0 && nx < 55 && ny >= 0 && ny < 55 && !used[nx][ny] && arr[nx][ny] == 1) {
used[nx][ny] = true;
dfs(nx, ny);
}
}
}
intmain(){
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);
int cnt = 0;
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;
return0;
}
BFS 解法:
#include<iostream>#include<vector>#include<queue>usingnamespace std;
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
voidbfs(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() &&
grid[nextY][nextX] == 1 && !used[nextY][nextX]) {
used[nextY][nextX] = true;
que.push({nextY, nextX});
}
}
}
}
intmain(){
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m));
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];
int result = 0;
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;
return0;
}
2. 岛屿的最大面积
在岛屿数量的基础上,计算组成岛屿的陆地总数,并取最大值。
#include<iostream>#include<cstring>#include<algorithm>usingnamespace std;
constint 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, max_area;
voiddfs(int x, int y){
for (int i = 0; i < 4; ++i) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx >= 0 && nx < N && ny >= 0 && ny < N && !used[nx][ny] && arr[nx][ny] == 1) {
used[nx][ny] = true;
cur_area++;
dfs(nx, ny);
}
}
}
intmain(){
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);
max_area = 0;
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;
return0;
}
3. 孤岛的总面积
孤岛是指完全被水域包围且不接触边缘的岛屿。思路是先标记所有接触边缘的岛屿,剩下的即为孤岛。
#include<iostream>#include<cstring>usingnamespace std;
constint 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};
voiddfs(int x, int y){
for (int i = 0; i < 4; ++i) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !used[nx][ny] && arr[nx][ny] == 1) {
used[nx][ny] = true;
dfs(nx, ny);
}
}
}
intmain(){
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] == 1) { used[i][0] = true; dfs(i, 0); }
if (!used[i][n - 1] && arr[i][n - 1] == 1) { used[i][n - 1] = true; dfs(i, n - 1); }
}
for (int i = 0; i < n; ++i) {
if (!used[0][i] && arr[0][i] == 1) { used[0][i] = true; dfs(0, i); }
if (!used[m - 1][i] && arr[m - 1][i] == 1) { 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;
return0;
}
#include<iostream>#include<cstring>usingnamespace std;
constint 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};
voiddfs(int cur_arr[N][N], int flag, int x, int y){
for (int i = 0; i < 4; ++i) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (cur_arr[nx][ny] != 0) continue;
// 水从高往低流,所以当前高度 >= 下一个高度if (arr[x][y] >= arr[nx][ny]) {
cur_arr[nx][ny] = flag;
dfs(cur_arr, flag, nx, ny);
}
}
}
intmain(){
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;
return0;
}
#include<iostream>#include<unordered_map>#include<unordered_set>usingnamespace std;
constint N = 55;
int n, m;
int arr[N][N];
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
voiddfs(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);
}
intmain(){
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) {
int cnt = 0;
dfs(i, j, mark++, cnt);
umap[mark - 1] = cnt;
}
int max_all = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (arr[i][j] == 0) {
unordered_set<int> uset;
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) {
// 如果没有 0,或者全是 0,需特殊处理,这里假设至少有一个 1// 若全为 0,则填一个得 1bool hasOne = false;
for(int i=0;i<n;++i) for(int j=0;j<m;++j) if(arr[i][j]==1) hasOne=true;
if(!hasOne) cout << 1 << endl;
else cout << umap[2] << endl; // 简化处理,实际应检查是否有未合并的岛
} else {
cout << max_all << endl;
}
return0;
}
7. 岛屿的周长
统计岛屿边长。只有"1"与"0"或边界的交界处计入周长。
#include<iostream>usingnamespace std;
constint 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;
voiddfs(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)
dfs(x + dir[i][0], y + dir[i][1]);
}
intmain(){
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;
return0;
}
return0;
}
#include<iostream>#include<unordered_map>#include<unordered_set>#include<queue>usingnamespace std;
boolget_cnt(string str1, string str2){
if (str1.size() != str2.size()) returnfalse;
int cnt = 0;
for (size_t i = 0; i < str1.size(); ++i)
if (str1[i] != str2[i]) cnt++;
return cnt == 1;
}
intmain(){
int n;
string begin_str, end_str;
cin >> n >> begin_str >> end_str;
unordered_set<string> uset;
for (int i = 0; i < n; ++i) {
string str;
cin >> str;
uset.insert(str);
}
queue<pair<string, int>> q;
q.emplace(begin_str, 1);
unordered_map<string, int> umap;
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;
return0;
}
for (auto& str_cur : uset) {
if (umap.find(str_cur) != umap.end()) continue;
if (!get_cnt(str, str_cur)) continue;
umap[str_cur] = cnt + 1;
q.emplace(str_cur, cnt + 1);
}
}
cout << 0 << endl;
return0;
}
9. 有向图的完全联通
判断从节点 1 是否能到达所有其他节点。使用邻接表和 DFS 即可。
#include<iostream>#include<cstring>#include<list>#include<vector>usingnamespace std;
constint N = 105;
int used[N];
vector<list<int>> graph(N);
int n, m;
voiddfs(int i){
if (used[i] != 0) return;
used[i] = 1;
for (int node : graph[i])
dfs(node);
}
intmain(){
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;
return0;
}
cout << 1 << endl;
return0;
}