题目重点:Senior Tech Screen 给 5×5 区域类型/皇冠格,按每个连通区域单独计算面积与皇冠总数。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 每格是一个区域类型字符加非负整数皇冠数,皇冠数可能不止一位;按上下左右四连通,不含对角。
- 同类型但不相邻的格子属于不同区域,各自算分;空棋盘返回 0,行宽一致。
解题路线
- 遍历每格,若未访问就以其类型启动 BFS/DFS;只走相同类型的四邻居并即时标 visited。
- 对每个连通块累计 areaCells 和 crowns,出队完毕把 areaCells×crowns 加入总分。
- 每格恰进入一个连通块,且搜索只沿同类型边扩展,所以找到的恰是该格所属的极大连通区域;各区域不重叠、覆盖全图。
- 测试单格 0 皇冠、同类型对角接触、长条区域、多位皇冠和多个隔开的 G 区域。
手动走一遍
题目首个 G 区域 4 格、皇冠总数 8,得 32;首个 W 区域 4 格、皇冠总数 2,得 8。需要继续遍历其余不相连区域并累加,而不是按类型把全图 G 全合并。
规模与取舍
R×C 棋盘每格只访问一次,O(RC) 时间;visited 与 BFS 队列最坏 O(RC) 空间,可原地标记则减少 visited 但会改输入。
易错点与追问
容易失分的边界
- 把对角接触视为相连。
- 按类型全局汇总而不是逐连通块。
- 用皇冠数之和替代面积×皇冠和。
- 假设 token 永远只有两字符,皇冠≥10 时解析错误。
继续深挖
- 若改成八连通怎么变?
- 棋盘局部更新时如何维护分数?
- 若区域值很大,如何避免递归栈溢出?
