链接: https://leetcode-cn.com/problems/pacific-atlantic-water-flow/
题意
给定一个二维的非负整数矩阵,每个位置的值表示海拔高度。假设左边和上边是太平洋,右边和下边是大西洋,求从哪些位置向下流水,可以流到太平洋和大西洋。水只能从海拔高的位置
流到海拔低或相同的位置。
解法
很显然是个搜索的题目了,但是如何进行搜索有个小trick,包括实现起来也有需要注意的地方
一开始我的做法是对所有的点都进行搜索,但是这种情况下时间复制度会比较高,而且之前的做法是搜索整个图判断是否能到达,实现起来也比较繁琐
一个比较简洁的解法是从边界开始向上流,经过的点都进行标记,这样可以减少搜索量,同时mark
矩阵和visit
矩阵可以用作相同的功能
代码
1 | class Solution { |