此题解采用了广度优先搜索（BFS）的方法来解决问题。首先，使用一个二维数组info来记录是否访问过每个单元格。初始时，将所有边界单元格以及所有的'0'（走廊）加入到搜索队列opts中，因为它们都与边界接壳。接下来，进行广度优先搜索，将与走廊相连的主题空间的每个部分标记为已访问。这一步确保了所有与走廊相连的区域都被标记。之后，再遍历数组，对于每一个未被访问的非走廊格子，从该位置出发进行广度优先搜索计算该区域的大小，并更新最大面积。最终返回最大的非与走廊相邻的主题空间面积。
时间复杂度: O(m*n)
空间复杂度: O(m*n)
class Solution:
def largestArea(self, grid: List[str]) -> int:
m = len(grid)
n = len(grid[0])
# 创建一个与grid大小相同的标记数组，记录是否访问过
info = [[0] * n for i in range(m)]
opts = [] # 队列，用于BFS
tmp_opts = None
# 初始化队列，包括所有边界单元格和'0'单元格
for j in range(n):
opts.append((0, j))
info[0][j] = 1
opts.append((m - 1, j))
info[m - 1][j] = 1
for i in range(1, m - 1):
opts.append((i, 0))
info[i][0] = 1
opts.append((i, n - 1))
info[i][n - 1] = 1
for j in range(1, n - 1):
if grid[i][j] == '0':
opts.append((i, j))
info[i][j] = 1
# 执行BFS以标记所有与走廊相邻的区域
while opts:
tmp_opts = []
for x, y in opts:
# 检查四个方向
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and (grid[x][y] == '0' or grid[nx][ny] == grid[x][y]) and info[nx][ny] == 0:
tmp_opts.append((nx, ny))
info[nx][ny] = 1
opts = tmp_opts
res = 0
# 计算最大非走廊相邻区域的大小
for i in range(1, m - 1):
for j in range(1, n - 1):
if info[i][j] == 0: # 未被标记的区域
tmp = 1
opts = [(i, j)]
info[i][j] = 1
while opts:
tmp_opts = []
for x, y in opts:
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == grid[x][y] and info[nx][ny] == 0:
tmp_opts.append((nx, ny))
info[nx][ny] = 1
tmp += 1
opts = tmp_opts
res = max(res, tmp)
return res