Given a N*N matrix contains lakes, each lake is represented by an elevation. The water in each lake can flow to its neighbours which has lower or equal elevations.
Suppose the left and top side of the matrix is surrounded by Pacific, the right and bottom is Atlantic.
Please write a function and return all lakes that can flow to both Pacific and Atlantic.
For example:
Pacific: ~ Atlantic: * ~ ~ ~ ~ ~ ~ ~ ~ 1 2 2 3 (5) * ~ 3 2 3 (4) (4) * ~ 2 4 (5) 3 1 * ~ (6) (7) 1 4 5 * ~ (5) 1 1 2 4 * * * * * * * *
The elements in parentheses are expected outputs:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
/* struct Point { int x{ 0 }, y{ 0 }; }; */ vector<vector<int>> dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}}; void dfs(vector<vector<int>>& mat, unordered_set<Point>& ocean, Point p) { int n = mat.size(); ocean.insert(p); for(auto& dir:dirs) { int x = p.x+dir[0]; int y = p.y+dir[1]; if(x<0 || y<0 || x>=n || y>=n || mat[x][y]<mat[p.x][p.y] || ocean.count({x,y})) continue; dfs(mat, ocean, {x,y}); } } vector<Point> flowing_water(vector<vector<int>>& mat) { unordered_set<Point> pac, atl; int n = mat.size(); for(int i=0; i<n; i++) { dfs(mat, pac, {0, i}); dfs(mat, pac, {i, 0}); dfs(mat, atl, {n-1, i}); dfs(mat, atl, {i, n-1}); } vector<Point> res; // unordered results // for(auto& p:atl) { // if(pac.count(p)) { // res.push_back(p); // } // } // ordered results for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { Point p = {i, j}; if(pac.count(p) && atl.count(p)) { res.push_back(p); } } } return res; }
相关推荐
32位超级流水灯.hex32位超级流水灯.hex32位超级流水灯.hex32位超级流水灯.hex
React 项目目录一、二、三、四、五、六、七、八、Redux-saga状态共享九、结尾十、Github链接一、技术栈详情可参阅 package.jsonYarnReact 16.9.0Redux-sagaReact RouterAxios 请求库Webpack 4.0+ES6 + BabelAntd项目...
We use 1650-nm femtosecond laser pulses to induce the plasma in a stable free-flowing water film under the strong field ionization mechanism. Moreover, we adopt intense terahertz (THz) pulses to ...
Terahertz (THz) waves could be generated through exciting a gravity-guided, free-flowing water wedge by a dual-color pulse. It is not required to rotate the optimal angle considering the water film as...
For the problem of tracking vehicles on freeways using machine vision, existing systems work well in free-flowing traffic. Traffic engineers, however, are more interested in monitoring freeways when ...
Streaming Data introduces the concepts and requirements of streaming and real-time... The book is an idea-rich tutorial that teaches you to think about how to efficiently interact with fast-flowing data.
流式计算的基础和原理 Streaming Data introduces the concepts and requirements of ... The book is an idea-rich tutorial that teaches you to think about how to efficiently interact with fast-flowing data.
Multiple Object Tracking by Flowing and Fusing
About the book Streaming Data is an idea-rich tutorial that teaches you to think about efficiently interacting with fast-flowing data. Through relevant examples and illustrated use cases, you'll ...
复杂网络上的信息不对称性流动,邵晨曦,豆慧玲,复杂网络中信息不对称的概念是基于经济学中的信息不对称原理和网络中的对称破缺提出的。一条链路上的两个节点之间的信息流动是双
Streaming Data is an idea-rich tutorial that teaches you to think about efficiently interacting with fast-flowing data. Through relevant examples and illustrated use cases, you’ll explore designs for...
遗传学、基因组学、蛋白质组学和生物信息学百科全书 4000页 彩色PDF清晰版。 作者: Jorde, Lynn B. (EDT) 出版社: John Wiley & Sons Inc 出版年: 2005-11 ...flowing in discovery." ELECTRIC REVIEW
~~ B O O K R E V I E W S GILBERT R. GREDLER University of South ... It is difficult to write a smooth-flowing text when so many individuals are involved, but overall this objective has been nicel
~~ B O O K R E V I E W S GILBERT R. GREDLER University of South ... It is difficult to write a smooth-flowing text when so many individuals are involved, but overall this objective has been nicel
对被动法T型(T-junc tion)、流动聚焦型(flow-focusing)和同轴环管型(co-flowing)3种微通道结构进行了说明,阐述了近年来这3种通道内两相动力学的研究进展,并对可大批量生成液滴的微流体芯片进行了介绍。同时对几种...
High-intensity laser–plasma interactions produce a wide array of energetic particles and beams with promising ... A novel nozzle assembly is used to generate high-velocity, laminar-flowing liquid micro
Hunted - A Flowing Editorial Magazine Theme 猎杀 - 流动的编辑杂志主题" ---------- 泰森云每天更新发布最新WordPress主题、HTML主题、WordPress插件、shopify主题、opencart主题、PHP项目源码、安卓项目源码、...
TLDR 网络演示: 鼠标和光标键移动。 地形 该项目旨在记录用于创建3维地形图及其可能的河道的简单算法。 其目的在于以计算上廉价的方式解决在程序生成的地形中创建可信的河流的问题。 在屏幕截图中,较暗的图块...
纤维悬浮湍流收缩流场中纤维取向分布和流变特性的计算,林建忠,,本文用雷诺应力模式求解雷诺平均运动方程,得到了具有矩形截面纤维悬浮湍流收缩流场中的平均速度和湍动能。然后将流场的湍流脉动