Flowing Water | tech::interview
优化的话，可以从两个ocean的点开始，从外往里搜。首先搜所有太平洋的点，记录下能接触到的position。然后同理搜大西洋的点，求出交集即可。
搜索用DFS和BFS都可以，复杂度为
https://moonstonelin.wordpress.com/2016/05/23/waterflow/
http://sidbai.github.io/2015/07/07/Flowing-Water/
http://yuanhsh.iteye.com/blog/2219621
输入是一个 N*N的矩阵，代表地势高度。如果下雨水流只能流去比他矮或者一样高的地势。
矩阵左边和上边是太平洋，右边和下边是大西洋。求出所有的能同时流到两个大洋的点。
For example:
|
|
括号里即为结果：
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
优化的话，可以从两个ocean的点开始，从外往里搜。首先搜所有太平洋的点，记录下能接触到的position。然后同理搜大西洋的点，求出交集即可。
搜索用DFS和BFS都可以，复杂度为
O(n^2)。
void search(Point pt, HashMap<Point,Boolean> visited, int[][] mat) {
int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
for(int i = 0; i < 4; ++i) {
int[] dir = dirs[i];
Point new_pt = new Point(dir[0] + pt.x, dir[1] + pt.y);
if( new_pt.x < 0 || new_pt.x >= mat.length || new_pt.y < 0 || new_pt.y >= mat.length ) {
continue;
}
if( mat[new_pt.x][new_pt.y] < mat[pt.x][pt.y] || visited.containsKey(new_pt) ) {
continue;
}
visited.put(new_pt, true);
search(new_pt, visited, mat);
}
}
public List<Point> flowing_water(int[][] mat) {
int n = mat.length;
// why not use hashset
HashMap<Point, Boolean> visited_pac = new HashMap<Point, Boolean>();
for(int i = 0; i < n; ++i) {
Point p = new Point(0,i);
visited_pac.put(p, true);
search(p, visited_pac, mat);
}
for(int i = 0; i < n; ++i) {
Point p = new Point(i,0);
visited_pac.put(p, true);
search(p, visited_pac, mat);
}
HashMap<Point, Boolean> visited_alt = new HashMap<Point, Boolean>();
for(int i = 0; i < n; ++i) {
Point p = new Point(n-1,i);
visited_alt.put(p, true);
search(p, visited_alt, mat);
}
for(int i = 0; i < n; ++i) {
Point p = new Point(i,n-1);
visited_alt.put(p, true);
search(p, visited_alt, mat);
}
ArrayList<Point> ret = new ArrayList<Point>();
for(Point key : visited_alt.keySet()) {
if(visited_pac.containsKey(key)) {
ret.add(key);
}
}
return ret;
}
void search(Point pt, HashMap<Point,Boolean> visited, int[][] mat) { int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}}; for(int i = 0; i < 4; ++i) { int[] dir = dirs[i]; Point new_pt = new Point(dir[0] + pt.x, dir[1] + pt.y); if( new_pt.x < 0 || new_pt.x >= mat.length || new_pt.y < 0 || new_pt.y >= mat.length ) { continue; } if( mat[new_pt.x][new_pt.y] < mat[pt.x][pt.y] || visited.containsKey(new_pt) ) { continue; } visited.put(new_pt, true); search(new_pt, visited, mat); } } public List<Point> flowing_water(int[][] mat) { int n = mat.length; HashMap<Point, Boolean> visited_pac = new HashMap<Point, Boolean>(); for(int i = 0; i < n; ++i) { Point p = new Point(0,i); visited_pac.put(p, true); search(p, visited_pac, mat); } for(int i = 0; i < n; ++i) { Point p = new Point(i,0); visited_pac.put(p, true); search(p, visited_pac, mat); } HashMap<Point, Boolean> visited_alt = new HashMap<Point, Boolean>(); for(int i = 0; i < n; ++i) { Point p = new Point(n-1,i); visited_alt.put(p, true); search(p, visited_alt, mat); } for(int i = 0; i < n; ++i) { Point p = new Point(i,n-1); visited_alt.put(p, true); search(p, visited_alt, mat); } ArrayList<Point> ret = new ArrayList<Point>(); for(Point key : visited_alt.keySet()) { if(visited_pac.containsKey(key)) { ret.add(key); } } return ret; }
https://moonstonelin.wordpress.com/2016/05/23/waterflow/
public List<Tuple<int, int>> WaterFlow(int[,] matrix){ HashSet<int> visited1 = new HashSet<int>(); HashSet<int> visited2 = new HashSet<int>(); HashSet<Tuple<int, int>> result1 = new HashSet<Tuple<int,int>>(); HashSet<Tuple<int, int>> result2 = new HashSet<Tuple<int,int>>(); List<Tuple<int, int>> result = new List<Tuple<int, int>>(); int R = matrix.GetLength(0); int C = matrix.GetLength(1); for (int c = 0; c < C; c++) { WaterFlowHelper(matrix, 0, c, visited1, result1); WaterFlowHelper(matrix, R - 1, c, visited2, result2); } for (int r = 0; r < R; r++) { WaterFlowHelper(matrix, r, 0, visited1, result1); WaterFlowHelper(matrix, r, C - 1, visited2, result2); } foreach (var tp in result1) { if (result2.Contains(tp)) { result.Add(tp); } } return result;}private void WaterFlowHelper(int[,] matrix, int row, int column, HashSet<int> visited, HashSet<Tuple<int, int>> result){ int R = matrix.GetLength(0); int C = matrix.GetLength(1); if ((row < 0) || (row >= R) || (column < 0) || (column >= C)) { return; } if (visited.Contains(row * R + column)) { return; } visited.Add(row * R + column); result.Add(new Tuple<int, int>(row, column)); int[] dirX = new int[4] { 0, -1, 0, 1 }; int[] dirY = new int[4] { -1, 0, 1, 0 }; for (int i = 0; i < 4; i++) { int X = row + dirX[i]; int Y = column + dirY[i]; if ((X >= 0) && (X < R) && (Y >= 0) && (Y < C) && (matrix[X, Y] >= matrix[row, column])) { WaterFlowHelper(matrix, X, Y, visited, result); } }}http://yuanhsh.iteye.com/blog/2219621
- 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;
- }
