[Google最新面试题] continental divider

给一个矩阵，其中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)