LeetCode LCS 03. 主题空间（广度优先搜索BFS）

Michael阿明

发布于 2021-09-06 11:13:01

2270

发布于 2021-09-06 11:13:01

文章被收录于专栏：Michael阿明学习之路

文章目录

- 1. 题目
- 2. 解题

1. 题目

「以扣会友」线下活动所在场地由若干主题空间与走廊组成，场地的地图记作由一维字符串型数组 grid，字符串中仅包含 “0"～"5” 这 6 个字符。地图上每一个字符代表面积为 1 的区域，其中 “0” 表示走廊，其他字符表示主题空间。相同且连续（连续指上、下、左、右四个方向连接）的字符组成同一个主题空间。

假如整个 grid 区域的外侧均为走廊。请问，不与走廊直接相邻的主题空间的最大面积是多少？如果不存在这样的空间请返回 0。

示例 1:
输入：grid = ["110","231","221"]
输出：1
解释：4 个主题空间中，只有 1 个不与走廊相邻，面积为 1。

示例 2:
输入：grid = ["11111100000","21243101111","21224101221","11111101111"]
输出：3
解释：8 个主题空间中，有 5 个不与走廊相邻，面积分别为 3、1、1、1、2，最大面积为 3。

提示：
1 <= grid.length <= 500
1 <= grid[i].length <= 500
grid[i][j] 仅可能是 "0"～"5"

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/YesdPw 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

先扫描一遍边界，以及和 0 相邻的位置，并以该位置开始 BFS
在扫描一遍就是剩余不跟走廊相邻的，记录最大面积

class Solution {
public:
    typedef pair<int,int> pii;
    vector<vector<int>> dir = {{1,0},{0,1},{-1,0},{0,-1}};
    
    int largestArea(vector<string>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(vis[i][j])
                    continue;
                if((i==0 || i==m-1 || j==0 || j==n-1) && grid[i][j] != '0')
                {	// 边界 且 不为 0，也是跟外侧连通的
                    bfs(grid, vis, m, n, i, j);
                }
                else if(grid[i][j] == '0')
                {	// 当前是 0, 检查周围的位置
                    vis[i][j] = true;
                    for(int k = 0; k < 4; ++k)
                    {
                        int nx = i + dir[k][0];
                        int ny = j + dir[k][1];
                        if(nx>=0 && nx<m && ny>=0 && ny<n && !vis[nx][ny] && grid[nx][ny] != '0')
                        {	// 周围的位置未访问，且不为 0，也是跟走廊相邻的
                            bfs(grid, vis, m, n, nx, ny);
                        }
                    }
                }
            }
        }
        int maxArea = 0;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {	// 剩余的不跟走廊相邻的区域
                if(vis[i][j]) continue;
                maxArea = max(maxArea, bfs(grid, vis, m, n, i, j));
            }
        }
        return maxArea;
    }
    int bfs(vector<string>& grid, vector<vector<bool>> &vis, int m, int n, int i, int j)
    {
        int area = 0;
        char color = grid[i][j]; // 颜色
        vis[i][j] = true;
        queue<pii> q;
        q.push({i, j});
        while(!q.empty())
        {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            area++;
            for(int k = 0; k < 4; ++k)
            {
                int nx = x + dir[k][0];
                int ny = y + dir[k][1];
                if(nx>=0 && nx<m && ny>=0 && ny<n && !vis[nx][ny] && grid[nx][ny]==color)
                {	// 在范围内，未访问，颜色一样
                    vis[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
        return area;
    }
};

2956 ms 376.2 MB C++

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/06/19 ，如有侵权请联系 cloudcommunity@tencent.com 删除

https