岛上雨水较多,如果相邻单元格的高度 小于或等于 当前单元格的高度,雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
对于相邻单元格,水可以从高的单元格流向低的单元格,水流分为两个方向,流向太平洋和流向大西洋,即向左和上流以及向右和下流,题目求的是同时能流向左上和右下的单元格的坐标集合。可以分开求能流向左上的单元格和能流向右下的单元格,两个集合求交集就是最终结果。
可以用BFS来做,流向右下的情况从左边界和上边界开始,向右下移动,记录符合条件的单元格坐标;流向左上的情况从右边界和下边界开始,向左上移动,记录符合条件的单元格坐标,最后对以上两个结果求交集就是最终答案。