网格中起始节点集到目标节点集的可达性映射求解

给定一个N×M大小的高度网格，每个单元格代表其高度。仅当相邻单元格高度更低时，可向当前单元格的上下左右方向移动。
首行所有单元格为起始节点集，末行所有单元格为目标节点集。需生成一个M×M的二进制矩阵，其中Matrix[i][j] = 1当且仅当从单元格(0, i)可以到达单元格(N-1, j)。

已知N、M ≤ 2000，单元格高度小于10^9。

已尝试的方法 #

• 观察结论：该网格实际是一个DAG（有向无环图）。
• 方法1：对首行每个单元格执行DFS，找出可到达的末行单元格。最坏情况下时间复杂度为O(N×M×M)，开销极高。
• 方法2：在方法1基础上进行记忆化，避免重复DFS，但每个单元格需存储可达的末行单元格，空间复杂度达O(N×M×M)，占用过大。
• 曾考虑使用DSU（并查集）但未找到正确用法，耗时多日仍无有效解决方案。

核心思路：反向拓扑排序 + 区间并查集优化 #

因为网格是DAG，我们可以反转移动规则（允许从低高度单元格向高高度单元格移动），将问题转化为：末行的每个单元格j，能反向到达首行的哪些i？此时Matrix[i][j] = 1等价于i在j的反向可达首行集合中。这种反向处理能让我们通过拓扑排序高效合并可达集合。

具体步骤

1. 拓扑排序准备：将所有单元格按高度从高到低排序。因为反向移动是从低到高，原DAG的反向图中，高高度单元格没有入边，优先处理。
2. 初始化可达集合：末行的每个单元格j，其反向可达的末行集合仅包含自身。用并查集维护每个位置所属的连续区间（记录区间左右端点），这样可以用近似O(1)的复杂度完成合并和查询。
3. 遍历合并集合：按高度从高到低处理每个单元格：
   • 遍历四个相邻单元格，如果相邻单元格的高度≥当前单元格（符合反向移动规则），则将当前单元格的可达区间合并到相邻单元格的可达区间中。
4. 生成结果矩阵：遍历首行的每个单元格i，检查末行的每个j是否在i的反向可达区间内，是则Matrix[i][j] = 1，否则为0。

时间复杂度分析

• 拓扑排序：O(N×M log(N×M))，排序N*M个元素的开销。
• 合并操作：每个单元格最多被四个方向的邻居合并一次，总操作数O(N×M)，并查集的路径压缩和按秩合并保证近似O(1)的单次操作。
• 结果生成：O(M×K)，K为每个首行单元格的可达区间数量，实际远小于M，整体复杂度完全适配N、M≤2000的规模。

替代思路：正向BFS + 动态规划

按高度从低到高处理单元格，维护每个单元格能正向到达的末行集合：

• 初始化：末行每个单元格j的可达集合为{j}。
• 遍历每个单元格，若相邻单元格高度更高（符合正向移动规则），则将当前单元格的可达区间合并到相邻单元格中。
• 最终首行每个单元格的可达区间就是结果矩阵对应的行。

内容的提问来源于stack exchange，提问作者Maggi Iggam