Uber VO 面试真题解析：Island Perimeter（岛屿周长）

You’re given an R-by-C array of integers that represents a top-down map of a building construction site, where each location in the array represents a one-meter by one-meter square of land. In this array, a 0 means that there will be nothing built on that square, and a 1 means that the building will include that square.

Assume that at most one building is planned for the site. Return the perimeter of that building.

Examples:

[[0, 0, 0, 0],
 [0, 1, 0, 0],
 [0, 0, 0, 0]] -> the perimeter of the building is 4.

[[0, 0, 0, 0, 0],
 [0, 1, 1, 0, 0],
 [0, 1, 1, 0, 0],
 [0, 0, 0, 0, 0]] -> the perimeter of the building is 8.

[[1, 0, 0, 0],
 [0, 0, 0, 0],
 [0, 0, 0, 0]] -> the perimeter of the building is 4.

[[1, 1, 1],
 [1, 0, 1],
 [1, 1, 1]] -> should return 12. We only count the 12m perimeter on the north/south/east/west, not the extra 4m perimeter that faces the internal courtyard.

[[1, 0, 1],
 [1, 0, 1],
 [1, 1, 1]] -> should return 14.

这道题本质上是计算二维网格中由 1 组成的建筑周长。最直接的做法是遍历每个为 1 的格子，把它的 4 条边都先算进去，然后检查四个方向是否与相邻建筑格子相连；每相邻一次，就要把共享的那条边减掉 1。这样既能正确处理单个方块，也能处理矩形、L 形以及带内部空洞的情况，因为只有外边界才计入周长。时间复杂度是 O(RC)，适合面试中快速实现。