2020-03-15 刷题1（深搜，栈）

695 岛屿的最大面积

标签：深度优先搜索，栈
开始我想的是为了避免重复搜索，每个位置只向右和下两个方向搜索。但是这样造成的问题是，对于H型的岛屿，右上的就不会被搜索到了。因此，需要在每个位置上对四个方向都进行搜索，已经搜索过一次的位置直接置0，避免重复搜索，同时也可以保证每个位置至少被搜索一次。由于每次都是四个方向穷尽搜索的，因此不用担心漏掉某个方向，从而错过最优解。
现在能用栈我就不想用递归了，因为重复调用函数有时间和栈空间的开销，并且如果递归过深，可能造成栈溢出。所以，采用深度优先搜索+栈的方式，每搜索到当前一个节点，将它四个方向上不为0的位置添加到栈中，等待下一次出栈搜索，直到栈为空，就结束了一个岛屿的搜索。
这里，设置了两个数组，dx和dy，记录四个方向的偏移。用这种方法可以简化代码，不用写四次if判断了。
时间复杂度：O(HW)， 空间复杂度O(HW)，当所有位置都是1时，达到最大的栈空间占用。

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int max_area = 0, cur_area = 0;
        int h = grid.size(), w = grid.size() ? grid[0].size():0;
        int dx[4] = {0, 0, 1, -1}, dy[4] = {-1, 1, 0, 0};
        stack<int> pos;
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                if(grid[i][j] == 0)
                    continue;
                pos.push(i);
                pos.push(j);
                grid[i][j] = 0;
                cur_area = 0;
                while(!pos.empty()){
                    int y = pos.top();
                    pos.pop();
                    int x = pos.top();
                    pos.pop();
                    for(int k = 0; k < 4; k++){
                        if(x + dx[k] >= 0 && x + dx[k] < h && y + dy[k] >= 0 && y + dy[k] < w && grid[x + dx[k]][y + dy[k]]){
                            pos.push(x + dx[k]);
                            pos.push(y + dy[k]);
                            grid[x + dx[k]][y + dy[k]] = 0;
                        }
                    }
                    cur_area++;
                }
                max_area = cur_area > max_area ? cur_area : max_area;
            }
        }
        return max_area;
    }
};

除了深度优先搜索+栈，还可以采用广搜+队列，结果是一样的。