网站建设注意细节问题,微信二维码,网站内容段落之间有空格对seo有影响吗,公司网站制作教学文章目录1. 题目2. 解题1. 题目
「以扣会友」线下活动所在场地由若干主题空间与走廊组成#xff0c;场地的地图记作由一维字符串型数组 grid#xff0c;字符串中仅包含 “0#xff5e;5” 这 6 个字符。 地图上每一个字符代表面积为 1 的区域#xff0c;其中 …
文章目录1. 题目2. 解题1. 题目
「以扣会友」线下活动所在场地由若干主题空间与走廊组成场地的地图记作由一维字符串型数组 grid字符串中仅包含 “05” 这 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] 仅可能是 05来源力扣LeetCode 链接https://leetcode-cn.com/problems/YesdPw 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
先扫描一遍边界以及和 0 相邻的位置并以该位置开始 BFS在扫描一遍就是剩余不跟走廊相邻的记录最大面积
class Solution {
public:typedef pairint,int pii;vectorvectorint dir {{1,0},{0,1},{-1,0},{0,-1}};int largestArea(vectorstring grid) {int m grid.size(), n grid[0].size();vectorvectorbool vis(m, vectorbool(n, false));for(int i 0; i m; i){for(int j 0; j n; j){if(vis[i][j])continue;if((i0 || im-1 || j0 || jn-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(nx0 nxm ny0 nyn !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(vectorstring grid, vectorvectorbool vis, int m, int n, int i, int j){int area 0;char color grid[i][j]; // 颜色vis[i][j] true;queuepii 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(nx0 nxm ny0 nyn !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阿明一起加油、一起学习进步
