695. 岛屿的最大面积

$$695.岛屿的最大面积$$

原题目

标签

$Stack$、深度优先搜索、方向变量、递归

带有注解的代码

class Solution {
public:

    vector<int> direction{-1,0,1,0,-1};
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        

        //深度优先遍历：
        //方法一：使用stack进行深度优先搜索
        int m = grid.size();                //行长度
        int n = m ? grid[0].size() : 0;     //列长度
        int local_area;                     //每次点(i,j)进行测试的时候存放最大值
        int area = 0;                       //存放最后的最大值
        int x;
        int y;

        for(int i = 0 ; i < m ; i++)            //从每个点开始进行遍历
        {
            for(int j = 0 ; j < n ; j++)
            {
                if(grid[i][j])              //如果这个点在当前地图中是陆地则可以开始进行拓展
                {
                    local_area = 1;         //算了初始脚下的这片面积了
                    grid[i][j] = 0;         //标志更改


                    //stack中使用的是二元组是为了保存的时候将两个坐标同时进行保存
                    stack<pair<int,int>> island;
                
                    island.push({i,j});        //首个陆地加入到栈中

                    while(!island.empty())      
                    {
                        auto [r,c] = island.top();      //取出栈顶元素
                        island.pop();
                        for(int k = 0 ; k < 4 ; k++)       //遍历四个方向
                        {
                            x = r + direction[k];
                            y = c + direction[k+1];
                            
                            //只有既不超过范围，并且也是陆地的方块才能够进行加入
                            if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1)
                            {
                                grid[x][y] = 0;
                                ++local_area;
                                island.push({x,y});
                            }
                        }
                    }
                    area = max(area,local_area);            //遍历完一个点之后取最值
                }
            }
        }
       return area;

------------------------------------------------------------------------------------

       //方法二：使用系统递归调用
        //调用递归主函数  
        if(grid.empty() || grid[0].empty())
            return 0;

        int max_area = 0;
        for(int i = 0 ; i < grid.size() ; i++)
        {
            for(int j = 0 ; j < grid[0].size() ; j++)
            {
                if(grid[i][j] == 1)
                    max_area = max(max_area,dfsTwo(grid,i,j));
                    //dfsOne(grid,i,j);
            }
        }

        return max_area;
    }

    //递归函数写法一：
    //拓展的时候顺带进行判断，如果不符合条件直接去除
    int dfsOne(vector<vector<int>>& grid , int r ,int c)
        {
            if(grid[r][c] == 0)
                return 0;
            
            grid[r][c] = 0;

            int x;
            int y;
            int area = 1;

            for(int i = 0 ; i < 4 ; i++)
            {
                x = r + direction[i];
                y = c + direction[i+1];

                //拓展的时候进行条件判断
                if(x >= 0 && x < grid.size() && y >= 0 && grid[0].size())       
                    area += dfsOne(grid,x,y);
            }
            return area;
        }

    //递归函数写法二：
    //拓展的时候直接拓展，之后进入到下一个递归层在判断这样拓展符不符合条件
    int dfsTwo(vector<vector<int>>& grid,int r,int c)
    {
        if(r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size() || grid[r][c] == 0)        //判断上一层是否符合条件
            return 0;
        grid[r][c] = 0;

        //直接递归省去了方向标志的创建
        return 1 + dfsTwo(grid,r + 1 ,c) + dfsTwo(grid,r - 1,c) + dfsTwo(grid,r,c + 1) + dfsTwo(grid,r,c - 1);
    }
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115