Question

请教一个关于C/C++中二维数组的问题，求详解。

问题如下：
一个n*m的矩阵M中，标记0为白色区域，标记1为黑色区域，白色区域代表可以行走的区域，黑色区域代表阻挡，可以知道，如果在这个矩阵中只有上、下、左、右移动，那么有些白色区域是不能到达的，我们称这样的矩阵是不能全相通的。
（1）如何验证一个矩阵是不是全相通？请给出算法思路。
（2）计算出你的算法的空间复杂度和时间复杂度。
（3）用C/C++编写出代码，并在适当的地方加上注释。
我想的是用递归遍历数组，如果遇到‘0’，就开始用递归，这种问题用递归最好了，把数组中的‘0’都设置成‘1’，再遍历数组，如果数组里有‘1’，就证明这个数组不是全相通的，否则是全相通的，但是这个有一个问题，那就是在调用递归的时候会重复遍历之前遍历过的节点，这样会加大时间和空间的开销。
求大神帮忙解答这三个问题，求详解！如果好，加分！

Answer 1

验证一个矩阵是不是全相通，你的算法是不是想复杂了。下面是我想法。
如果一个矩阵不是全相通的，那么必定存在一个黑色区域相连至边缘。将白色区域分割掉。因此问题就转换为矩阵中是否存在这样的黑色区域。因此在二维数组中可以这样：
1）先扫描第一位数组，若没有黑色区域，那么扫描第二维的时候只要看首尾有没有黑色区域，若没有依次类推。
2）若有黑色区域，那么扫描下一维，只要看相对上一维的黑色区域相邻位置是否有黑色区域，若没有，上面都作废，因此肯定连通，若有的话依次。。
3）。。。。
实现起来的空间复杂度和时间复杂度应该不会很大。。。。。

Answer 2

初始化，设置集合C，初始时为空

随便第一个标记为0的区域，加入C

while C!=空集：
取出C中一个元素e

add neighbors(up down right left) of e marked as 0 to C, C= C-e.Mark e as 2.
end while

最后扫描一遍矩阵，如果有0，则非全连通，否则是全连通，即0都变成了2.
C可以用一个栈或者队列来实现。

追问

不好意思，你这个我没怎么看懂，找到一个标记为0的区域，把它加入C，是把什么加入C？最后还是从某一个标记为0的区域递归的扫描局部相通的区域，把她变成2，那设置集合C又有什么作用呢？求详解！

追答

随便找到一个0，比如它的编号是i，把这个位置加入C。
假设这个矩阵可以被赋值，如果不能赋值，就复制一份。在while循环之后，矩阵的内容就改变了。如果是全连通，里面的0应该都变成了2。
其实跟你的思路差不多，C就是用来防止重复扫描的。把被扫描过的点标记为2，在while循环中就不会被们加入C了。

Answer 3

来看答案的~

Answer 4

晕，这么大量的数据，空间使用G来衡量，肯定没有足够的内存。为了给你一个想法：
定义一个指针数组，* P [100000]，每个元素指向100,000个元素的数组，数组中的磁盘上的文件，需要解决的学生档案，文件的过程写完了，每次只有一个阵列读取到内存中，或创建一个队列，队列满时，一队。