给定一个由 0/1 组成的矩阵,翻转至多一个 0 为 1,使得矩阵中相连(上下左右)的 1 形成的最大连通区域面积最大。分两步处理:
1 的格子,使用深度优先或广度优先(DFS/BFS)将整片连通区域标记为同一个 id(从 2 开始,避开 0/1),同时统计该岛屿的面积。id 对应的面积保存到哈希表 area[id] 中。ShopeeExpress的包裹配送站在东南亚某国覆盖了一部分区域。如果有两个区域是相邻的,或者可以经过一系列相邻的区域连通起来,包裹在这两个区域中的传递成本就非常低,否则成本会非常高。
为了节约成本,同一连通区域的面积应当尽可能大。
为了简化问题,我们把地图看作一个二维矩阵,每个区域就是其中的一个元素,一个区域的上下左右