力扣竞赛微爱思扣(下)

这是我参与更文挑战的第22天，活动详情查看：更文挑战

LCS 03. 主题空间

思路分析

这道题和岛屿问题十分的类似，都可以用深度优先搜索或广度优先搜索来解决。题干中描述场地外围和‘0’的地方均为走廊，因此我们就可以将传统岛屿问题的非法地址和grid[i][j] == 0当作一类情况处理。

题目要求我们求出不与走廊直接相邻的主题空间的最大面积：

1. 这就需要我们分别计算出每个主题空间的面积，
2. 相对于传统的0-1分布的岛屿，由于该题会出现12345等5种1，因此我们要判断是否他的左右上下的点是和该点相同的1（也就是dfs需要多一个参数）
3. 由于要排除掉不与走廊直接相邻的主题空间，因此我们要设置一个flag，如果flag为1，则不统计该结果
4. 最初我以为统计最大需要放入一个数组中，最后比一次大小，但其实仅仅需要维持一个max整数型变量就可以了。

代码

class Solution {
public:
    int largestArea(vector<string>& grid) {
        vector<int> ret;
        int max = 0;
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[0].size(); j++){
                
                if(grid[i][j] != '6' && grid[i][j] != '0'){
                    // cout << i << " " << j << endl;
                    ret.push_back(0);
                    int count = 0;
                    dfs(grid, i, j, count, grid[i][j], ret);
                    if(ret[ret.size() - 1] == -1){
                        ret.pop_back();
                    }else{
                        ret[ret.size() - 1] = count;
                        if(max < count) max = count;
                    }
                }
            }
        }
        return max;
    }
    void dfs(vector<string>& grid, int x, int y, int& count,char ca, vector<int>& ret){ 
        if(x < 0 || x > grid.size() - 1 || y < 0 || y > grid[0].size() - 1|| grid[x][y] == '0'){
            ret[ret.size() - 1] = -1;
            return ;
        }
        // cout << x<< " :" << y << endl;
        if(grid[x][y] != ca)return ;
        grid[x][y] = '6';
        count++;
        dfs(grid, x + 1, y, count, ca, ret);
        dfs(grid, x - 1, y, count, ca, ret);
        dfs(grid, x, y + 1, count, ca, ret);
        dfs(grid, x, y - 1, count, ca, ret);

    }
};
复制代码