算法 : martix traversal variation

Question

有一个N×N的正方形网状网格线，如下图所示。网格的节点位于点 (X, Y)，其中 X 和 Y 是从 0 到 N-1 的整数。电流流过网格，位于 (0, 0) 和 (N−1, N−1) 的节点之间。

最初，所有的电线都传导电流，但电线以每秒一根的速度烧毁。倦怠由三个零索引整数数组 A、B 和 C 描述，每个数组的大小为 M。对于每个时刻 T (0 ≤ T < M)，在第 T 秒节点之间的连线 (A[T ], B[T]) 和:

    (A[T], B[T] + 1), if C[T] = 0 or
    (A[T] + 1, B[T]), if C[T] = 1

烧坏了。您可以假设这些阵列描述了现有的电线，并且没有电线多次烧坏。您的任务是确定电流何时停止在 (0,0) 和 (N−1,N−1) 处的节点之间流动。

写一个函数:

int wire_burnouts(int N, int A[], int M, int B[], int M2, int C[], int M3); 

给定整数 N 和数组 A、B 和 C，返回电流在 (0, 0) 和 (N−1, N−1) 节点之间停止流动之前的秒数。如果在所有 M 线烧毁后电流继续流动，则函数应返回 -1。

例如，给定 N = 4，M = 9 和以下数组:

A[0] = 0 B [0] = 0 C[0] = 0
1 = 1 B 1 = 1 C 1 = 1
2 = 1 B 2 = 1 C 2 = 0
A[3] = 2 B [3] = 1 C[3] = 0
A[4] = 3 B [4] = 2 C[4] = 0
A[5] = 2 B [5] = 2 C[5] = 1
A[6] = 1 B [6] = 3 C[6] = 1
A[7] = 0 B [7] = 1 C[7] = 0
A[8] = 0 B [8] = 0 C[8] = 1

您的函数应返回 8，因为就在第八根电线烧断后，(0, 0) 和 (N−1, N−1) 的节点之间没有连接。这种情况如下图所示:

给定 N = 4，M = 1 和以下数组:

A[0] = 0 B [0] = 0 C[0] = 0

您的函数应返回 −1，因为烧断单根导线不会断开 (0, 0) 和 (N−1, N−1) 处节点之间的连接。

假设:

    N is an integer within the range [1..400];
    M is an integer within the range [0..2*N*(N−1)];
    each element of array A is an integer within the range [0..N−1];
    each element of array B is an integer within the range [0..N−1];
    each element of array C is an integer within the range [0..1].

复杂度:

    expected worst-case time complexity is O(N2*log(N));
    expected worst-case space complexity is O(N2), beyond input storage (not counting the storage required for input arguments).

Answer 1

构建完整的电线网格。然后销毁前 M/2 根电线。使用深度优先搜索检查连通性。如果仍然连接，再销毁 M/4 根电线。如果没有，恢复最近损坏的 M/4 电线。继续这种二进制搜索，直到找到合适的 T。

时间复杂度由深度优先搜索的次数决定:O(log M) <= O(log N) 和每个深度优先搜索的复杂度:O(N²)。

---

以前的结果可能会通过 Disjoint-set data structure 得到改善.

构建完整的电线网格。然后按照数组A、B、C的指示销毁M条线。将网格的剩余连通分量添加到不相交集数据结构中。

然后按顺序恢复连线，从这些数组的最后一个元素开始到它们的第一个元素。在这样做的同时，找到不相交集结构中剩余的集合的并集。当包含节点 (0, 0) 和 (N−1, N−1) 的集合连接在一起时停止。

如果disjoint-set数据结构使用按秩联合和路径压缩方法，整个算法的时间复杂度为O(N² α(N))，其中 α 是反阿克曼函数。这实际上与 O(N²) 一样好。

---

如果我们使用一个图，可以改进之前的结果，对偶到原始网格线:对偶图的节点对应于原始图的面，对偶图的每条边与原始图的相应边相交。将需要两个额外的节点:节点 L 连接到对偶图的每个顶部和左侧节点，节点 R 连接到每个底部和右侧节点。

如果此对偶图包含从 L 到 R 的路径，则节点 (0, 0) 和 (N−1, N−1) 无法相互连接。如果没有从L到R的路径，则节点(0, 0)和(N−1, N−1)相连。

最初对偶图是完全断开的。在从原始图中删除边的同时，我们将相应的边添加到对偶图中。同时更新不相交集数据结构。一旦包含节点 L 和 R 的集合连接在一起，就停止。

此算法只需访问其输入数组 A、B 和 C 的元素一次，这使其成为 Online algorithm .

时间复杂度的最大限制因素现在是对偶图节点数组的初始化时间:O(N²)。如果有一种方法可以避免这种初始化，我们将得到渐近更高效的 O(M α(M)) 算法。有几种解决初始化问题的方法:

• 使用this trick在 O(1) 时间内初始化数组。这给出了 O(M α(M)) 最坏情况时间算法。但在实践中，几乎不可能在不初始化的情况下分配内存(出于安全原因)。
• 初始化数组一次，然后多次使用该算法。这给出了 O(M α(M)) 摊销时间算法。
• 使用哈希表存储对偶图的节点。这给出了 O(M α(M)) 期望时间算法。这也将空间复杂度提高到 O(M)。