题目描述
「以扣会友」线下活动所在场地由若干主题空间与走廊组成,场地的地图记作由一维字符串型数组 grid
,字符串中仅包含 "0"~"5"
这 6 个字符。地图上每一个字符代表面积为 1
的区域,其中 "0"
表示走廊,其他字符表示主题空间。相同且连续(连续指上、下、左、右四个方向连接)的字符组成同一个主题空间。
假如整个 grid
区域的外侧均为走廊。请问,不与走廊直接相邻的主题空间的最大面积是多少?如果不存在这样的空间请返回 0
。
样例
输入:grid = ["110","231","221"]
输出:1
解释:4 个主题空间中,只有 1 个不与走廊相邻,面积为 1。
输入: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"
算法
(深度优先遍历) $O(mn)$
- 深度优先遍历找到每个非
0
连通块。 - 如果某个连通块不与
0
或者边界相邻,则更新答案。
时间复杂度
- 每个位置最多被遍历一次,故总时间复杂度为 $O(mn)$。
空间复杂度
- 需要 $O(mn)$ 的额外空间存储系统栈。
C++ 代码
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
class Solution {
private:
int m, n;
bool ok;
int current, counter;
void dfs(int x, int y, vector<string> &grid) {
if (x == 0 || x == m - 1 || y == 0 || y == n - 1)
ok = false;
counter++;
grid[x][y] = 'x';
for (int i = 0; i < 4; i++) {
int tx = x + dx[i], ty = y + dy[i];
if (tx < 0 || tx >= m || ty < 0 || ty >= n)
continue;
if (grid[tx][ty] == '0')
ok = false;
if (grid[tx][ty] != current)
continue;
dfs(tx, ty, grid);
}
}
public:
int largestArea(vector<string>& grid) {
m = grid.size();
n = grid[0].size();
int ans = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (grid[i][j] == '0' || grid[i][j] == 'x')
continue;
current = grid[i][j];
ok = true;
counter = 0;
dfs(i, j, grid);
if (ok)
ans = max(ans, counter);
}
return ans;
}
};