【Day45 LeetCode】图论题目 Ⅲ
一、图论题目 Ⅲ1、淹没孤岛
这题只能从边界开始扩散，将靠近边界的陆地标志，表示不是孤岛，最后将孤岛淹没，将不是孤岛标志回陆地。
# include<iostream>
# include<vector>
using namespace std;
void dfs(vector<vector<int>> &graph, int i, int j){
if(i<0 || i>=graph.size() || j<0 || j>=graph.size() || graph!=1)
return;
graph = 2;
dfs(graph, i+1, j);
dfs(graph, i-1, j);
dfs(graph, i, j+1);
dfs(graph, i, j-1);
}
int main(){
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n, vector<int>(m));
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)
cin >> graph;
// 步骤一：
// 从左侧边，和右侧边 向中间遍历
for (int i = 0; i < n; i++) {
if (graph == 1) dfs(graph, i, 0);
if (graph == 1) dfs(graph, i, m - 1);
}
// 从上边和下边 向中间遍历
for (int j = 0; j < m; j++) {
if (graph == 1) dfs(graph, 0, j);
if (graph == 1) dfs(graph, n - 1, j);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (graph == 1) graph = 0;
if (graph == 2) graph = 1;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << graph << " ";
}
cout << endl;
}
return 0;
}
2、水流题目
如果想着从当前点向两个边界移动的话，时间复杂度过高，因为需要遍历每个点，每个点又需要扩散到两个边界。如果我们逆向思维，想着从边界出发去找可达的点，这一下就豁然开朗了。
# include<iostream>
# include<vector>
using namespace std;
vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void dfs(vector<vector<int>> &graph, vector<vector<bool>> &vis,int ii, int jj){
if(vis)
return;
vis = true;
for(auto xy : dirs){
int i = ii + xy, j = jj + xy;
if(i<0 || i>=graph.size() || j<0 || j>=graph.size() || graph > graph || vis)
continue;
dfs(graph, vis, i, j);
}
}
int main(){
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n, vector<int>(m));
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)
cin >> graph;
vector<vector<bool>> vis1(n, vector<bool>(m, false));
vector<vector<bool>> vis2(n, vector<bool>(m, false));
for(int i=0; i<n; ++i){
dfs(graph, vis1, i, 0);
dfs(graph, vis2, i, m-1);
}
for(int i=0; i<m; ++i){
dfs(graph, vis1, 0, i);
dfs(graph, vis2, n-1, i);
}
for(int i=0; i<n; ++i){
for(int j=0; j<m; ++j){
if(vis1 && vis2)
cout << i << " " << j << endl;
}
}
return 0;
}
3、建造最大岛屿
写了个很不优雅的代码，思路是 DFS遍历陆地，给每个岛屿一一对应的编号，并用哈希表记载编号与岛屿面积的对应关系。然后，第二次遍历图，碰到水域，遍历水域的四个方向上的编号，举行面积聚加，一个细节是需要用set举行去重，可能四个反向上存在编号雷同的区域。
# include<iostream>
# include<vector>
# include<unordered_map>
# include<unordered_set>
using namespace std;
int dfs(vector<vector<int>> &graph, int i, int j, int num){
if(i<0 || i>=graph.size() || j<0 || j>=graph.size() || graph!=1)
return 0;
graph = num;
return 1 + dfs(graph, i+1, j, num)+ dfs(graph, i-1, j, num)+ dfs(graph, i, j+1, num)+ dfs(graph, i, j-1, num);
}
int main(){
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n, vector<int>(m));
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)
cin >> graph;
unordered_map<int, int> mp; // 映射几号陆地 与 其面积关系
mp = 0;
int idx = 2; // 几号陆地
int ans = 0;
for(int i=0; i<n; ++i){
for(int j=0; j<m; ++j){
if(graph==1){
mp = dfs(graph, i, j, idx);
ans = max(ans, mp);
++idx;
}
}
}
vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for(int i=0; i<n; ++i){
for(int j=0; j<m; ++j){
if(graph==0){
int tmp = 1;
unordered_set<int> set;
for(auto xy : dirs){
int x = i + xy, y = j + xy;
if(x>=0 && x<n && y>=0 && y<m && set.find(graph)==set.end()){
set.insert(graph);
tmp += mp];
}
}
ans = max(ans, tmp);
}
}
}
cout << ans << endl;
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]