目录
Leetcode695. 岛屿的最大面积
文章链接：代码随想录
题目链接：695. 岛屿的最大面积
思路：dfs
class Solution {
public:
int count;
int dir[4][2] = {
1, 0, -1, 0, 0, 1, 0, -1};
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){
for (int i = 0; i < 4; i++){
int nex = x + dir[i][0];
int ney = y + dir[i][1];
if (nex < 0 || nex >= grid.size() || ney < 0 || ney >= grid[0].size()) continue;
if (!visited[nex][ney] && grid[nex][ney] == 1){
visited[nex][ney] = true;
count++;
dfs(grid, visited, nex, ney);
}
}
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
int result = 0;
vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), 0));
for (int i = 0; i < grid.size(); i++){
for (int j = 0; j < grid[0].size(); j++){
if (!visited[i][j] && grid[i][j] == 1){
visited[i][j] = true;
count = 1;
dfs (grid, visited, i, j);
result = max(result, count);
}
}
}
return result;
}
};
bfs
class Solution {
public:
int count;
int dir[4][2] = {
1, 0, -1, 0, 0, 1, 0, -1};
void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){
queue<pair<int, int>> que;
que.push({
x, y});
while(!que.empty()){
pair<int, int> cur = que.front();
que.pop();
for (int i = 0; i < 4; i++){
int nex = cur.first + dir[i][0];
int ney = cur.second + dir[i][1];
if (nex < 0 || nex >= grid.size() || ney < 0 || ney >= grid[0].size()) continue;
if (!visited[nex][ney] && grid[nex][ney] == 1){
visited[nex][ney] = true;
count++;
que.push({
nex, ney});
}
}
}
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
int result = 0;
vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), 0));
for (int i = 0; i < grid.size(); i++){
for (int j = 0; j < grid[0].size(); j++){
if (!visited[i][j] && grid[i][j] == 1){
visited[i][j] = true;
count = 1;
bfs (grid, visited, i, j);
result = max(result, count);
}
}
}
return result;
}
};
Leetcode1020. 飞地的数量
文章链接：代码随想录
题目链接：1020. 飞地的数量
思路：dfs
class Solution {
public:
int count = 0;
int dir[4][2] = {
1, 0, -1, 0, 0, 1, 0, -1};
void dfs(vector<vector<int>>& grid, int x, int y){
grid[x][y] = 0;
count++;
for (int i = 0; i < 4; i++){
int nex = x + dir[i][0];
int ney = y + dir[i][1];
if (nex < 0 || nex >= grid.size() || ney < 0 || ney >= grid[0].size()) continue;
if (grid[nex][ney] == 1) dfs(grid, nex, ney);
}
return ;
}
int numEnclaves(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
int result = 0;
for (int i = 0; i < m; i++){
if(grid[i][0] == 1) dfs(grid, i, 0);
if(grid[i][n - 1] == 1) dfs(grid, i, n - 1);
}
for (int j = 0; j < n; j++){
if (grid[0][j] == 1) dfs(grid, 0, j);
if (grid[m - 1][j] == 1) dfs(grid, m - 1, j);
}
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (grid[i][j] == 1) {
count = 0;
dfs(grid, i, j);
result += count;
}
}
}
return result;
}
};
Leetcode130. 被围绕的区域
文章链接：代码随想录
题目链接：130. 被围绕的区域
思路：dfs
class Solution {
public:
int dir[4][2] = {
1, 0, -1, 0, 0, 1, 0, -1};
void dfs(vector<vector<char>>& board, int x, int y){
board[x][y] = 'A';
for (int i = 0; i < 4; i++){
int nex = x + dir[i][0];
int ney = y + dir[i][1];
if (nex < 0 || nex >= board.size() || ney < 0 || ney >= board[0].size()) continue;
if (board[nex][ney] == 'O') dfs(board, nex, ney);
}
}
void solve(vector<vector<char>>& board) {
int m = board.size();
int n = board[0].size();
for (int i = 0; i < m; i++){
if (board[i][0] == 'O') dfs(board, i, 0);
if (board[i][n - 1] == 'O') dfs(board, i, n - 1);
}
for (int j = 0; j < n; j++){
if (board[0][j] == 'O') dfs(board, 0, j);
if (board[m - 1][j] == 'O') dfs(board, m - 1, j);
}
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (board[i][j] == 'O') board[i][j] = 'X';
if (board[i][j] == 'A') board[i][j] = 'O';
}
}
}
};
Leetcode417. 太平洋大西洋水流问题
文章链接：代码随想录
题目链接：417. 太平洋大西洋水流问题
思路：注意终止条件 if (visited[x][y]) return ;
class Solution {
public:
int dir[4][2] = {
1, 0, -1, 0, 0, 1, 0, -1};
void dfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, int x, int y){
// 注意终止条件
if (visited[x][y]) return ;
visited[x][y] = true;
for (int i = 0; i < 4; i++){
int nex = x + dir[i][0];
int ney = y + dir[i][1];
if (nex < 0 || nex >= heights.size() || ney < 0 || ney >= heights[0].size()) continue;
if (heights[x][y] <= heights[nex][ney]) dfs(heights, visited, nex, ney);
}
}
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
int m = heights.size();
int n = heights[0].size();
vector<vector<bool>> pacific(m, vector<bool>(n, false));
vector<vector<bool>> atlantic(m, vector<bool>(n, false));
vector<vector<int>> result;
for (int i = 0; i < m; i++){
dfs(heights, pacific, i, 0);
dfs(heights, atlantic, i, n - 1);
}
for (int j = 0; j < n; j++){
dfs(heights, pacific, 0, j);
dfs(heights, atlantic, m - 1, j);
}
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (pacific[i][j] && atlantic[i][j]) result.push_back({
i, j});
}
}
return result;
}
};
Leetcode827.最大人工岛
思路：dfs，先用map记录原有的每块陆地的大小，再在0处遍历连接陆地，选择最大值。
class Solution {
public:
int count;
int mark = 2;
int dir[4][2] = {
1, 0, -1, 0, 0, 1, 0, -1};
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){
if (visited[x][y] || grid[x][y] == 0) return ;
visited[x][y] = true;
count++;
grid[x][y] = mark;
for (int i = 0; i < 4; i++){
int nex = x + dir[i][0];
int ney = y + dir[i][1];
if (nex < 0 || nex >= grid.size() || ney < 0 || ney >= grid[0].size()) continue;
dfs(grid, visited, nex, ney);
}
}
int largestIsland(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
unordered_map<int, int> gridNum;
bool isAllGrid = true;
int result = 0;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (grid[i][j] == 0) isAllGrid = false;
if (!visited[i][j] && grid[i][j] == 1){
count = 0;
dfs(grid, visited, i, j);
gridNum[mark] = count;
mark++;
}
}
}
// cout << count << endl;
// cout << gridNum[2] << endl;
if (isAllGrid) return n * m;
unordered_set<int> visitedGrid;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
visitedGrid.clear();
if (grid[i][j] == 0){
count = 1;
for (int k = 0; k < 4; k++){
int nex = i + dir[k][0];
int ney = j + dir[k][1];
if (nex < 0 || nex >= grid.size() || ney < 0 || ney >= grid[0].size()) continue;
if (visitedGrid.count(grid[nex][ney]) == 0){
count += gridNum[grid[nex][ney]];
visitedGrid.insert(grid[nex][ney]);
}
}
result = max(result, count);
}
}
}
return result;
}
};
图论第二天打卡，整体来说套路感挺重的，理解和做起来挺简单的，但写多了也头晕哈哈，加油！！！
