Google最新面试题
给一个矩阵，其中0代表海洋，其他数字代表高度，秉着水往低处流的原则，求出能够流向任意海洋的点。 比如说
0 0 0 1 2 3 0
0 1 2 2 4 3 2
2 1 1 3 3 2 0
0 3 3 3 2 3 3
那么就要给出 第二行的4 (这有这点出发，能够找到连通道四个0的区域的一条非递增路线)，当然也有可能找不到这样的点，或者找到多个点。
小编解答：
题目类型TAG：
图论，搜索，并集，扩散染色
一句话思路：
从原题矩阵中建立一个有向图，其中结点是矩阵中等高联通区域，而有向边连接的这些结点在矩阵中所代表的联通区域相邻，其方向是从底高度节点指向高高度结点;我们从低高度结点到高高度结点遍历整个有向图，并在遍历中不断地对汇入当前节点的海洋节点求并集;最后包括所有海洋节点的节点便是所求的节点。
详细步骤：
1. 建立所有有向图节点：通过遍历矩阵，我们可以找到所有的相邻的高度一样的区域。我们把每一个这样的区域组成一个有向图的节点，用这个区域的高度来标识这个节点的.高度。要注意的是，我们要在原矩阵的每个元素上记录其所属的有向图节点，以便于下一步中建立有向边。这些有向图的节点里面还应包括一个bitset，以便第三步中进行对其能到达海洋求并集。给每一个高度为0 的有向图节点的bitset里面set一个unique 的bit。
2. 建立节点有向边: 再次遍历矩阵，这次注意所遍历元素的上下左右所有相邻元素。如果这些相邻元素和当前元素属于不同有向图的节点，则通过有向边连接他们，边的方向是由底高度节点指向高高度节点。在设置有向边的时候，要注意去除重复的边。
3. 遍历有向图：将有向图从底到顶遍历。遍历的时候，将前导节点的bitset 并入当前节点，如果当前节点的bitset中包括所有的海洋bits，那么当前节点就标记为成功节点。
4. 得出答案：再一次遍历原矩阵里面的所有元素，如果某个元素所属的有向图节点是成功节点，那么这个元素也就是属于所要找的点。
时间复杂度分析：
由于步骤1，2，3, 4 的复杂度都是O(n),n表示矩阵中的元素个数，那么最后的整体时间复杂度也是O(n)
http://www.cnrencai.com/