100.岛屿的最大面积
dfs
#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){visited[nextx][nexty] = 1;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;visited[i][j] = true;dfs(grid, visited, i, j);result = max(result, count);}}}cout<<result<<endl;
}bfs
#include <iostream>
#include <vector>
#include <queue>
using namespace std;int count;
int dir[4][2] = {0,1,1,0,-1,0,0,-1};
void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){queue<int> que;que.push(x);que.push(y);visited[x][y] = true;count++;while(!que.empty()){int xx = que.front(); que.pop();int yy = que.front(); que.pop();for(int i=0; i<4; i++){int nextx = xx + dir[i][0];int nexty = yy + dir[i][1];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;count++;que.push(nextx);que.push(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 = vector<vector<bool>>(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=0;bfs(grid, visited, i, j);result = max(result, count);}}}cout << result << endl;
}101. 孤岛的总面积
给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。
现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。
本题要求找到不靠边的陆地面积，那么我们只要从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋，然后再去重新遍历地图 统计此时还剩下的陆地就可以了。
#include <bits/stdc++.h>
using namespace std;int my_count;
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
void dfs(vector<vector<int>>&grid, int x, int y){grid[x][y] = 0;my_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;if(grid[nextx][nexty]==0) continue;dfs(grid, nextx, nexty);}return;
}
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];}}for(int i=0; i<n; i++){if(grid[i][0]==1) dfs(grid, i, 0);if(grid[i][m-1]==1) dfs(grid, i, m-1);}for(int j=0; j<m; j++){if(grid[0][j]==1) dfs(grid, 0, j);if(grid[n-1][j]==1) dfs(grid, n-1, j);}my_count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) dfs(grid, i, j);}}cout << my_count << endl;
}dijkstra（朴素版）精讲
#include <bits/stdc++.h>
using namespace std;int main(){int n, m, p1, p2, val;cin>>n>>m;vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid[p1][p2] = val;}int start = 1;int end = n;vector<int> minDist(n+1, INT_MAX);vector<int> visited(n+1, false);minDist[start] = 0;for(int i=1; i<= n; i++){int minVal = INT_MAX;int cur = 1;for(int v=1; v<= n; v++){if(!visited[v]&&minDist[v]<minVal){minVal = minDist[v];cur = v;}}visited[cur] = true;for(int v=1; v<=n; v++){if(!visited[v]&&grid[cur][v]!=INT_MAX&&minDist[cur] + grid[cur][v] < minDist[v]){minDist[v] = minDist[cur] + grid[cur][v];}}}if(minDist[end]==INT_MAX) cout<<-1<<endl;//不能到终点else cout<<minDist[end]<<endl;
}