water flow days – Moonstone
题目就是给你一个matrix，里面的数字代表bar的高度，现在说降雨量如果高于bar的高度水可以漫过去，降雨量0开始每天+1这样，问最早第几天水可以有一条路径从src漫到dst
这轮也是讨论optimization很久，最后用bfs写一个subproblem。
http://www.1point3acres.com/bbs/thread-191771-1-1.html
第三题是不是就是lc 174. Dungeon Game的变种？DP从dst开始做？
这道题常规解法是O(max(day)*n^2) 当mat里有个别bar相当高的时候那么day by day增长的模式会造成大量空转 所以一个办法来避免是先把所有bar寻到一个数组并排好序 然后每当bfs到某几个bar不能再move的时候 我们从那个数组里找到某天天数大于当前bound某个bar 然后继续bfs到不能再走 这样一直到找到终点 这样总能最早到达目的地因为每次bfs完我们都是从那个数组里找到下一个最早能继续move的时间。
不是给了src和destination吗？楼主的意思是如果bfs到某个点走不动了，直接跳到下一个点继续bfs吗？这样可以吗？
我的想法是贪心+BFS,一旦有路就走到下面去，没有就选四个里面最小的那个走下去
是的 就是从那个排好序的数字搜索下一个直接跳 其实找下一个的这个时间复杂度我感觉是降不下来的 好像面试官也这么认为..
先假设这个问题是一维的，那么从src能够淹没到dst的日期取决于他俩之间最高的bar的高度。
转换为一个matrix的话，我们其实就是要找一条从src到dst的路径，这条路径上最高bar的高度越小越好。然后最短日期其实就是这条路径上最高bar的高度+1。
我们可以用BFS，然后把一般BFS其中的queue换成priority queue，在priority queue顶端的是当前未走过的高度最小的bar的index。
Read full article from water flow days – Moonstone
题目就是给你一个matrix，里面的数字代表bar的高度，现在说降雨量如果高于bar的高度水可以漫过去，降雨量0开始每天+1这样，问最早第几天水可以有一条路径从src漫到dst
这轮也是讨论optimization很久，最后用bfs写一个subproblem。
http://www.1point3acres.com/bbs/thread-191771-1-1.html
第三题是不是就是lc 174. Dungeon Game的变种？DP从dst开始做？
这道题常规解法是O(max(day)*n^2) 当mat里有个别bar相当高的时候那么day by day增长的模式会造成大量空转 所以一个办法来避免是先把所有bar寻到一个数组并排好序 然后每当bfs到某几个bar不能再move的时候 我们从那个数组里找到某天天数大于当前bound某个bar 然后继续bfs到不能再走 这样一直到找到终点 这样总能最早到达目的地因为每次bfs完我们都是从那个数组里找到下一个最早能继续move的时间。
不是给了src和destination吗？楼主的意思是如果bfs到某个点走不动了，直接跳到下一个点继续bfs吗？这样可以吗？
我的想法是贪心+BFS,一旦有路就走到下面去，没有就选四个里面最小的那个走下去
是的 就是从那个排好序的数字搜索下一个直接跳 其实找下一个的这个时间复杂度我感觉是降不下来的 好像面试官也这么认为..
先假设这个问题是一维的，那么从src能够淹没到dst的日期取决于他俩之间最高的bar的高度。
转换为一个matrix的话，我们其实就是要找一条从src到dst的路径，这条路径上最高bar的高度越小越好。然后最短日期其实就是这条路径上最高bar的高度+1。
我们可以用BFS，然后把一般BFS其中的queue换成priority queue，在priority queue顶端的是当前未走过的高度最小的bar的index。
int leastDays(const pair<int, int>& src, const pair<int, int>& dst, const vector<vector<int>>& matrix) const {
const vector<pair<int, int>> directions{ { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
int n = matrix.size();
if (n == 0) {
return 0;
}
int m = matrix.size();
if (m == 0) {
return 0;
}
int highest = 0;
auto comp = [&](const node& rhs, const node& lhs){ return rhs.value != lhs.value ? rhs.value > lhs.value : rhs.index > lhs.index; };
unordered_set<pair<int, int>, MyHash> visited;
priority_queue<node, vector<node>, decltype(comp)> q;
visited.insert(src);
q.emplace(src, matrix[src.first][src.second]);
while (!q.empty()) {
auto p = q.top();
q.pop();
if (p.value > highest) {
highest = p.value;
}
for (const auto& d : directions) {
pair<int, int> next(p.index.first + d.first, p.index.second + d.second);
if (next.first >= 0 && next.first < n && next.second >= 0 && next.second < m && visited.find(next) == visited.end()) {
if (next == dst) {
highest = max(highest, matrix[dst.first][dst.second]);
return highest + 1;
}
int next_value = matrix[next.first][next.second];
q.emplace(next, next_value);
visited.insert(next);
}
}
}
return highest + 1;
}
struct MyHash {
inline std::size_t operator()(const std::pair<int, int>& p) const {
return (hash<int>()(p.first) + hash<int>()(p.second));
}
};
struct node {
pair<int, int> index;
int value;
node(pair<int, int> idx, int val) : index(idx), value(val) {}
};
};
public void TestMinDaysOfWaterFlow() { int[,] matrix1 = new int[,] { {5, 8, 15, 20}, {13, 7, 3, 1}, {9, 10, 8, 4} }; int r1 = MinDaysOfWaterFlow(matrix1, 0, 0, 2, 3); } public int MinDaysOfWaterFlow(int[,] matrix, int startRow, int startColumn, int endRow, int endColumn) { int result = int.MaxValue; Stack<Tuple<int, int>> stack = new Stack<Tuple<int, int>>(); HashSet<int> visited = new HashSet<int>(); MinDaysOfWaterFlowHelper(matrix, ref result, ref matrix[startRow, startColumn], startRow, startColumn, endRow, endColumn, visited, stack); return result; } private void MinDaysOfWaterFlowHelper(int[,] matrix, ref int result, ref int curMax, int startRow, int startColumn, int endRow, int endColumn, HashSet<int> visited, Stack<Tuple<int, int>> stack) { int R = matrix.GetLength(0); int C = matrix.GetLength(1); if ((startRow == endRow) && (startColumn == endColumn)) { if ((result == int.MaxValue) || (curMax < result)) { result = curMax; } return; } int index = startRow * R + startColumn; visited.Add(index); 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 = startRow + dirX[i]; int y = startColumn + dirY[i]; if ((x >= 0) && (x < R) && (y >= 0) && (y < C) && (!visited.Contains(x * R + y))) { if ((result != int.MaxValue) && (matrix[x, y] >= result)) { continue; } int preCurMax = curMax; if (matrix[x, y] >= curMax) { curMax = matrix[x, y]; } stack.Push(new Tuple<int, int>(x, y)); MinDaysOfWaterFlowHelper(matrix, ref result, ref curMax, x, y, endRow, endColumn, visited, stack); stack.Pop(); if (matrix[x, y] == curMax) { curMax = preCurMax; } } } visited.Remove(index); }}