l********r
发帖数: 140 | |
f****s
发帖数: 74 | 2 难道不是和一维类似吗？
先每一行从左到又扫，再从右到左扫。得到两个矩阵
然后每一列从上到下扫，再从下到上扫，得到两个矩阵。
然后扫一遍矩阵。 |
l*n
发帖数: 529 | 3 a quick thought: locate ridges, which divide the matrix into wells, then
recurssively merge adjacent wells.
【在 l********r 的大作中提到】
: This one:
: http://leetcode.com/groups/twitter-interview/forum/topic/rain-w
: Don't see any good way so far.
|
p*****2
发帖数: 21240 | 4
你是每个cell只考虑四个方向吗？
【在 f****s 的大作中提到】
: 难道不是和一维类似吗？
: 先每一行从左到又扫，再从右到左扫。得到两个矩阵
: 然后每一列从上到下扫，再从下到上扫，得到两个矩阵。
: 然后扫一遍矩阵。
|
l**b
发帖数: 457 | 5 这个肯定不对吧。
我的考虑是从最外一圈开始扫描，存一个used的map，然后在扫描的结果里面取最小值
，如果没有就随便取一个，然后从那个点开始做4向的DFS或者BSF，如果这个点的值小
于当前的值，求差，存近result里面，然后在used map里面mark这个点。如果这个点的
值大于当前的值，标记一下这个点，用于下一轮求最小值，因为这个是一个新的border
了。
一直重复这个知道所有的点都在used map里面mark了。
好像很复杂的样子。。。
【在 p*****2 的大作中提到】
:
: 你是每个cell只考虑四个方向吗？
|
p*****2
发帖数: 21240 | 6
border
我也觉得不行。我的想法是用两个数据结构
1. visited matrix 表明已经用过的cell
2. PriorityQueue放目前的边界
PQ总是弹出最低的cell。得到最低的cell以后找没有访问过的邻居。如果邻居小的话，
就可以装水了。把邻居放入PQ中作为新的边界。
这样一直到PQ为空。复杂度N*N*logN, 程序貌似不是很复杂。
【在 l**b 的大作中提到】
: 这个肯定不对吧。
: 我的考虑是从最外一圈开始扫描，存一个used的map，然后在扫描的结果里面取最小值
: ，如果没有就随便取一个，然后从那个点开始做4向的DFS或者BSF，如果这个点的值小
: 于当前的值，求差，存近result里面，然后在used map里面mark这个点。如果这个点的
: 值大于当前的值，标记一下这个点，用于下一轮求最小值，因为这个是一个新的border
: 了。
: 一直重复这个知道所有的点都在used map里面mark了。
: 好像很复杂的样子。。。
|
p*****2
发帖数: 21240 | |
c********t
发帖数: 5706 | 8 你写的太简洁了，佩服。原来真的不用刻意删除PQ里的元素啊。
我想的是visited的应该从pq里删除。又想pq删除效率不高，就改用hashmap.还得每次
遍历找map里的最小值。真是越走越偏啊。比你复杂好多。但你觉得效率是不是高些？
BTW, welcome back to java!
【在 p*****2 的大作中提到】
: 写了一个。大家看看如果没什么问题。放到我的博客里去。
: http://blog.sina.com.cn/s/blog_b9285de20101j9a7.html
|
|
f****s
发帖数: 74 | |
c********t
发帖数: 5706 | 10 二爷，我和你的codes还有一个区别
你的check只查一个点，然后放入min heap. 我考虑的是，如果check的点比curr min小
，肯定就是new min,所以直接从它继续check. 只有比curr min大的点才入heap.所以我
是直接把dfs写到check里了。你觉得是不是效率高一点？
【在 p*****2 的大作中提到】
: 写了一个。大家看看如果没什么问题。放到我的博客里去。
: http://blog.sina.com.cn/s/blog_b9285de20101j9a7.html
|
|
|
p*****2
发帖数: 21240 | 11
应该没什么大区别吧。只是你这个就不需要enqueue，一直小的情况应该并不多见，代
码会复杂一些吧？
【在 c********t 的大作中提到】
: 二爷，我和你的codes还有一个区别
: 你的check只查一个点，然后放入min heap. 我考虑的是，如果check的点比curr min小
: ，肯定就是new min,所以直接从它继续check. 只有比curr min大的点才入heap.所以我
: 是直接把dfs写到check里了。你觉得是不是效率高一点？
|
c********t
发帖数: 5706 | 12 嗯，那在check method里，visited过得直接从min heap里去掉，有没有效率提升？（
见我上上帖子）
【在 p*****2 的大作中提到】
:
: 应该没什么大区别吧。只是你这个就不需要enqueue，一直小的情况应该并不多见，代
: 码会复杂一些吧？
|
p*****2
发帖数: 21240 | 13
应该没有什么大关系吧？
【在 c********t 的大作中提到】
: 嗯，那在check method里，visited过得直接从min heap里去掉，有没有效率提升？（
: 见我上上帖子）
|
p*****2
发帖数: 21240 | 14
想知道你怎么这么扣性能呀？
一般来说面试性能的提升主要是复杂度的改善，比赛的时候只要时间规定之内能过就行
，不用扣的很死。一般写代码之前能算个大概。
【在 c********t 的大作中提到】
: 嗯，那在check method里，visited过得直接从min heap里去掉，有没有效率提升？（
: 见我上上帖子）
|
c********t
发帖数: 5706 | 15 你说得对，我有点走火入魔了。
★ 发自iPhone App: ChineseWeb 7.8
【在 p*****2 的大作中提到】
:
: 想知道你怎么这么扣性能呀？
: 一般来说面试性能的提升主要是复杂度的改善，比赛的时候只要时间规定之内能过就行
: ，不用扣的很死。一般写代码之前能算个大概。
|
f*****w
发帖数: 52 | 16 我有个疑问， 假设如下的情况
3 3 3 3
3 0 0 3
3 1 3 3
第一次从queue里面弹出的是1， 找邻居的话会加入0进入队列。然后更新count = 1 -
0 = 1
但是在循环的时候会弹出0，邻居还是0， 此时程序不会算出第二个0那里可以放1的水。
我感觉应该一直DFS直到找不到比弹出元素更小的邻居。
【在 p*****2 的大作中提到】
:
: 想知道你怎么这么扣性能呀？
: 一般来说面试性能的提升主要是复杂度的改善，比赛的时候只要时间规定之内能过就行
: ，不用扣的很死。一般写代码之前能算个大概。
|
p*****2
发帖数: 21240 | 17
-
水。
你是对的。我update了一下逻辑。你看看怎么样。
【在 f*****w 的大作中提到】
: 我有个疑问， 假设如下的情况
: 3 3 3 3
: 3 0 0 3
: 3 1 3 3
: 第一次从queue里面弹出的是1， 找邻居的话会加入0进入队列。然后更新count = 1 -
: 0 = 1
: 但是在循环的时候会弹出0，邻居还是0， 此时程序不会算出第二个0那里可以放1的水。
: 我感觉应该一直DFS直到找不到比弹出元素更小的邻居。
|
h***i
发帖数: 1970 | 18 这个是对的，二爷牛蛙
【在 p*****2 的大作中提到】
:
: -
: 水。
: 你是对的。我update了一下逻辑。你看看怎么样。
|
H****r
发帖数: 2801 | 19 这题有oj么？
【在 l********r 的大作中提到】
: This one:
: http://leetcode.com/groups/twitter-interview/forum/topic/rain-w
: Don't see any good way so far.
|
H****r
发帖数: 2801 | 20 2爷 v5 这个是java?
【在 p*****2 的大作中提到】
: 写了一个。大家看看如果没什么问题。放到我的博客里去。
: http://blog.sina.com.cn/s/blog_b9285de20101j9a7.html
|
|
|
p*****2
发帖数: 21240 | 21
java。你需要scala的吗？怎么好久没见你了。
【在 H****r 的大作中提到】
: 2爷 v5 这个是java?
|
p*****2
发帖数: 21240 | 22
多谢大牛。
【在 h***i 的大作中提到】
: 这个是对的，二爷牛蛙
|
h***i
发帖数: 1970 | 23 应该有O(n*n)的解，第一步从周围向中间扫描，标注所有能流到外面的点，所有未标注
的点组成很多group, 但是每个group都被标注点包围，这就转化成surrounded region
problem. 第二步，在每个没有被标注的点dfs，找到包围这个未标注group的最小高度
。每个未标注group只用找一次。
【在 l********r 的大作中提到】
: This one:
: http://leetcode.com/groups/twitter-interview/forum/topic/rain-w
: Don't see any good way so far.
|
l*******b
发帖数: 2586 | |
d****n
发帖数: 233 | 25 Paste a solution with O(mn) complexity(coded in c#):
static int FindMaxWater(int[,] matrix, int m, int n)
{
// a 2d array with same size as matrix to hold maxim waters
int[,] potentialWater = new int[m, n];
List sequence = new List();
for (int i = 0; i < m; ++i)
{
// Find the ascending sequence from left to right
sequence.Clear();
sequence.Add(0);
for (int j = 1; j < n; ++j)
{
if (matrix[i, j] >= matrix[i, sequence.Last()])
{
sequence.Add(j);
}
}
int current = 0;
for(int k = 1; k
{
while(current < sequence[k])
{
potentialWater[i, current] = matrix[i, sequence[k-1]]
- matrix[i, current];
++current;
}
}
// Find the ascending sequence from right to left
sequence.Clear();
sequence.Add(n-1);
for (int j = n-2; j >=0; --j)
{
if (matrix[i, j] >= matrix[i, sequence.Last()])
{
sequence.Add(j);
}
}
current = n-1;
for(int k = 1; k
{
while(current > sequence[k])
{
potentialWater[i, current] = matrix[i, sequence[k-1]] -
matrix[i, current];
--current;
}
}
}
for (int j = 0; j < n; ++j)
{
// Find the ascending sequence from top to bottom
sequence.Clear();
sequence.Add(0);
for (int i = 1; i < m; ++i)
{
if (matrix[i, j] >= matrix[sequence.Last(), j])
{
sequence.Add(i);
}
}
int current = 0;
for(int k = 1; k
{
while(current < sequence[k])
{
potentialWater[current, j] = Math.Min(potentialWater[
current, j], matrix[sequence[k-1], j] - matrix[current, j]);
++current;
}
}
// Find the ascending sequence from bottom to top
sequence.Clear();
sequence.Add(m-1);
for (int i = m-2; i >=0; --i)
{
if (matrix[i, j] >= matrix[sequence.Last(), j])
{
sequence.Add(i);
}
}
current = m-1;
for(int k = 1; k
{
while(current > sequence[k])
{
potentialWater[current, j] = Math.Min(potentialWater[
current, j], matrix[sequence[k-1], j] - matrix[current, j]);
--current;
}
}
}
int ret = 0;
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
ret += potentialWater[i, j];
}
}
return ret;
}
【在 l*******b 的大作中提到】
: 赞一个! 这种问题感觉用fp反倒不好写了
|
H****r
发帖数: 2801 | 26 嗯嗯嗯那
【在 p*****2 的大作中提到】
:
: 多谢大牛。
|
l********r
发帖数: 140 | 27
"如果邻居小的话", "如果邻居低的话", is "小" same as "低"?
【在 p*****2 的大作中提到】
:
: 多谢大牛。
|
p*****2
发帖数: 21240 | 28
嗯。
【在 l********r 的大作中提到】
:
: "如果邻居小的话", "如果邻居低的话", is "小" same as "低"?
|
s**x
发帖数: 7506 | 29
多谢！ 我感觉那个check 可能要更复杂一些， 比如说， rectangle 四个角上的 cell
应该是没用的， 它们两侧相邻的 cell 应该足可以 hold water 了。
【在 p*****2 的大作中提到】
: 写了一个。大家看看如果没什么问题。放到我的博客里去。
: http://blog.sina.com.cn/s/blog_b9285de20101j9a7.html
|
l********r
发帖数: 140 | |
|
|
f****s
发帖数: 74 | 31 难道不是和一维类似吗？
先每一行从左到又扫，再从右到左扫。得到两个矩阵
然后每一列从上到下扫，再从下到上扫，得到两个矩阵。
然后扫一遍矩阵。 |
l*n
发帖数: 529 | 32 a quick thought: locate ridges, which divide the matrix into wells, then
recurssively merge adjacent wells.
【在 l********r 的大作中提到】
: This one:
: http://leetcode.com/groups/twitter-interview/forum/topic/rain-w
: Don't see any good way so far.
|
p*****2
发帖数: 21240 | 33
你是每个cell只考虑四个方向吗？
【在 f****s 的大作中提到】
: 难道不是和一维类似吗？
: 先每一行从左到又扫，再从右到左扫。得到两个矩阵
: 然后每一列从上到下扫，再从下到上扫，得到两个矩阵。
: 然后扫一遍矩阵。
|
l**b
发帖数: 457 | 34 这个肯定不对吧。
我的考虑是从最外一圈开始扫描，存一个used的map，然后在扫描的结果里面取最小值
，如果没有就随便取一个，然后从那个点开始做4向的DFS或者BSF，如果这个点的值小
于当前的值，求差，存近result里面，然后在used map里面mark这个点。如果这个点的
值大于当前的值，标记一下这个点，用于下一轮求最小值，因为这个是一个新的border
了。
一直重复这个知道所有的点都在used map里面mark了。
好像很复杂的样子。。。
【在 p*****2 的大作中提到】
:
: 你是每个cell只考虑四个方向吗？
|
p*****2
发帖数: 21240 | 35
border
我也觉得不行。我的基本思路：用两个数据结构
1. visited matrix 表明已经用过的cell
2. PriorityQueue放目前的边界
PQ总是弹出最低的cell。得到最低的cell以后找没有访问过的邻居。如果邻居小的话，
就可以装水了。把邻居放入PQ中作为新的边界(如果邻居低的话，用当前height代替邻
居的高度）。这样一直到PQ为空。复杂度N*N*logN, 程序不是很复杂。
【在 l**b 的大作中提到】
: 这个肯定不对吧。
: 我的考虑是从最外一圈开始扫描，存一个used的map，然后在扫描的结果里面取最小值
: ，如果没有就随便取一个，然后从那个点开始做4向的DFS或者BSF，如果这个点的值小
: 于当前的值，求差，存近result里面，然后在used map里面mark这个点。如果这个点的
: 值大于当前的值，标记一下这个点，用于下一轮求最小值，因为这个是一个新的border
: 了。
: 一直重复这个知道所有的点都在used map里面mark了。
: 好像很复杂的样子。。。
|
p*****2
发帖数: 21240 | |
c********t
发帖数: 5706 | 37 你写的太简洁了，佩服。原来真的不用刻意删除PQ里的元素啊。
我想的是visited的应该从pq里删除。又想pq删除效率不高，就改用hashmap.还得每次
遍历找map里的最小值。真是越走越偏啊。比你复杂好多。但你觉得效率是不是高些？
BTW, welcome back to java!
【在 p*****2 的大作中提到】
: 写了一个。大家看看如果没什么问题。放到我的博客里去。
: http://blog.sina.com.cn/s/blog_b9285de20101j9a7.html
|
f****s
发帖数: 74 | |
c********t
发帖数: 5706 | 39 二爷，我和你的codes还有一个区别
你的check只查一个点，然后放入min heap. 我考虑的是，如果check的点比curr min小
，肯定就是new min,所以直接从它继续check. 只有比curr min大的点才入heap.所以我
是直接把dfs写到check里了。你觉得是不是效率高一点？
【在 p*****2 的大作中提到】
: 写了一个。大家看看如果没什么问题。放到我的博客里去。
: http://blog.sina.com.cn/s/blog_b9285de20101j9a7.html
|
p*****2
发帖数: 21240 | 40
应该没什么大区别吧。只是你这个就不需要enqueue，一直小的情况应该并不多见，代
码会复杂一些吧？
【在 c********t 的大作中提到】
: 二爷，我和你的codes还有一个区别
: 你的check只查一个点，然后放入min heap. 我考虑的是，如果check的点比curr min小
: ，肯定就是new min,所以直接从它继续check. 只有比curr min大的点才入heap.所以我
: 是直接把dfs写到check里了。你觉得是不是效率高一点？
|
|
|
c********t
发帖数: 5706 | 41 嗯，那在check method里，visited过得直接从min heap里去掉，有没有效率提升？（
见我上上帖子）
【在 p*****2 的大作中提到】
:
: 应该没什么大区别吧。只是你这个就不需要enqueue，一直小的情况应该并不多见，代
: 码会复杂一些吧？
|
p*****2
发帖数: 21240 | 42
应该没有什么大关系吧？
【在 c********t 的大作中提到】
: 嗯，那在check method里，visited过得直接从min heap里去掉，有没有效率提升？（
: 见我上上帖子）
|
p*****2
发帖数: 21240 | 43
想知道你怎么这么扣性能呀？
一般来说面试性能的提升主要是复杂度的改善，比赛的时候只要时间规定之内能过就行
，不用扣的很死。一般写代码之前能算个大概。
【在 c********t 的大作中提到】
: 嗯，那在check method里，visited过得直接从min heap里去掉，有没有效率提升？（
: 见我上上帖子）
|
c********t
发帖数: 5706 | 44 你说得对，我有点走火入魔了。
★ 发自iPhone App: ChineseWeb 7.8
【在 p*****2 的大作中提到】
:
: 想知道你怎么这么扣性能呀？
: 一般来说面试性能的提升主要是复杂度的改善，比赛的时候只要时间规定之内能过就行
: ，不用扣的很死。一般写代码之前能算个大概。
|
f*****w
发帖数: 52 | 45 我有个疑问， 假设如下的情况
3 3 3 3
3 0 0 3
3 1 3 3
第一次从queue里面弹出的是1， 找邻居的话会加入0进入队列。然后更新count = 1 -
0 = 1
但是在循环的时候会弹出0，邻居还是0， 此时程序不会算出第二个0那里可以放1的水。
我感觉应该一直DFS直到找不到比弹出元素更小的邻居。
【在 p*****2 的大作中提到】
:
: 想知道你怎么这么扣性能呀？
: 一般来说面试性能的提升主要是复杂度的改善，比赛的时候只要时间规定之内能过就行
: ，不用扣的很死。一般写代码之前能算个大概。
|
p*****2
发帖数: 21240 | 46
-
水。
你是对的。我update了一下逻辑。你看看怎么样。
【在 f*****w 的大作中提到】
: 我有个疑问， 假设如下的情况
: 3 3 3 3
: 3 0 0 3
: 3 1 3 3
: 第一次从queue里面弹出的是1， 找邻居的话会加入0进入队列。然后更新count = 1 -
: 0 = 1
: 但是在循环的时候会弹出0，邻居还是0， 此时程序不会算出第二个0那里可以放1的水。
: 我感觉应该一直DFS直到找不到比弹出元素更小的邻居。
|
h***i
发帖数: 1970 | 47 这个是对的，二爷牛蛙
【在 p*****2 的大作中提到】
:
: -
: 水。
: 你是对的。我update了一下逻辑。你看看怎么样。
|
H****r
发帖数: 2801 | 48 这题有oj么？
【在 l********r 的大作中提到】
: This one:
: http://leetcode.com/groups/twitter-interview/forum/topic/rain-w
: Don't see any good way so far.
|
H****r
发帖数: 2801 | 49 2爷 v5 这个是java?
【在 p*****2 的大作中提到】
: 写了一个。大家看看如果没什么问题。放到我的博客里去。
: http://blog.sina.com.cn/s/blog_b9285de20101j9a7.html
|
p*****2
发帖数: 21240 | 50
java。你需要scala的吗？怎么好久没见你了。
【在 H****r 的大作中提到】
: 2爷 v5 这个是java?
|
|
|
p*****2
发帖数: 21240 | 51
多谢大牛。
【在 h***i 的大作中提到】
: 这个是对的，二爷牛蛙
|
h***i
发帖数: 1970 | 52 应该有O(n*n)的解，第一步从周围向中间扫描，标注所有能流到外面的点，所有未标注
的点组成很多group, 但是每个group都被标注点包围，这就转化成surrounded region
problem. 第二步，在每个没有被标注的点dfs，找到包围这个未标注group的最小高度
。每个未标注group只用找一次。
【在 l********r 的大作中提到】
: This one:
: http://leetcode.com/groups/twitter-interview/forum/topic/rain-w
: Don't see any good way so far.
|
l*******b
发帖数: 2586 | |
d****n
发帖数: 233 | 54 Paste a solution with O(mn) complexity(coded in c#):
static int FindMaxWater(int[,] matrix, int m, int n)
{
// a 2d array with same size as matrix to hold maxim waters
int[,] potentialWater = new int[m, n];
List sequence = new List();
for (int i = 0; i < m; ++i)
{
// Find the ascending sequence from left to right
sequence.Clear();
sequence.Add(0);
for (int j = 1; j < n; ++j)
{
if (matrix[i, j] >= matrix[i, sequence.Last()])
{
sequence.Add(j);
}
}
int current = 0;
for(int k = 1; k
{
while(current < sequence[k])
{
potentialWater[i, current] = matrix[i, sequence[k-1]]
- matrix[i, current];
++current;
}
}
// Find the ascending sequence from right to left
sequence.Clear();
sequence.Add(n-1);
for (int j = n-2; j >=0; --j)
{
if (matrix[i, j] >= matrix[i, sequence.Last()])
{
sequence.Add(j);
}
}
current = n-1;
for(int k = 1; k
{
while(current > sequence[k])
{
potentialWater[i, current] = matrix[i, sequence[k-1]] -
matrix[i, current];
--current;
}
}
}
for (int j = 0; j < n; ++j)
{
// Find the ascending sequence from top to bottom
sequence.Clear();
sequence.Add(0);
for (int i = 1; i < m; ++i)
{
if (matrix[i, j] >= matrix[sequence.Last(), j])
{
sequence.Add(i);
}
}
int current = 0;
for(int k = 1; k
{
while(current < sequence[k])
{
potentialWater[current, j] = Math.Min(potentialWater[
current, j], matrix[sequence[k-1], j] - matrix[current, j]);
++current;
}
}
// Find the ascending sequence from bottom to top
sequence.Clear();
sequence.Add(m-1);
for (int i = m-2; i >=0; --i)
{
if (matrix[i, j] >= matrix[sequence.Last(), j])
{
sequence.Add(i);
}
}
current = m-1;
for(int k = 1; k
{
while(current > sequence[k])
{
potentialWater[current, j] = Math.Min(potentialWater[
current, j], matrix[sequence[k-1], j] - matrix[current, j]);
--current;
}
}
}
int ret = 0;
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
ret += potentialWater[i, j];
}
}
return ret;
}
【在 l*******b 的大作中提到】
: 赞一个! 这种问题感觉用fp反倒不好写了
|
H****r
发帖数: 2801 | 55 嗯嗯嗯那
【在 p*****2 的大作中提到】
:
: 多谢大牛。
|
l********r
发帖数: 140 | 56
"如果邻居小的话", "如果邻居低的话", is "小" same as "低"?
【在 p*****2 的大作中提到】
:
: 多谢大牛。
|
p*****2
发帖数: 21240 | 57
嗯。
【在 l********r 的大作中提到】
:
: "如果邻居小的话", "如果邻居低的话", is "小" same as "低"?
|
s**x
发帖数: 7506 | 58
多谢！ 我感觉那个check 可能要更复杂一些， 比如说， rectangle 四个角上的 cell
应该是没用的， 它们两侧相邻的 cell 应该足可以 hold water 了。
【在 p*****2 的大作中提到】
: 写了一个。大家看看如果没什么问题。放到我的博客里去。
: http://blog.sina.com.cn/s/blog_b9285de20101j9a7.html
|
d****n
发帖数: 233 | 59 I posted the O(mn)at http://codeanytime.blogspot.com/
cell
【在 s**x 的大作中提到】
:
: 多谢！ 我感觉那个check 可能要更复杂一些， 比如说， rectangle 四个角上的 cell
: 应该是没用的， 它们两侧相邻的 cell 应该足可以 hold water 了。
|
g*********e
发帖数: 14401 | 60 // follow physics law to fill the cubes with rain drops
void fillWater(int & arr[][], int x, int y, int & dropCount);
// bfs search to see if (x,y) is the local lowest, if so, fill all area with
the same height as (x,y), to the height of lowest edge surrounding it,
update arr[][] to simulate fill water, and count the total drops filled. If
(x,y) not the local lowest, do nothing.
int fill(int &arr[][], int x, int y){
int dropCount=0;
int preDropCount=0;
do{
for(int i=1;i
for(int j=1;j
fillWater(arr, i, j, dropCount);
}while(preDropCount < dropCount);
return dropCount;
} |
|
|
s**x
发帖数: 7506 | 61
正在看这个题，发现关键是弹出来的那个位置可能起不到边界的作用了。 比如假设(0,
0) 位置最低，但它不起任何作用，因为(0,1) 和（1，0） 就可以挡住水了，所以 (0,
0) 应该直接忽略。
同样比如
ABCD
EFGH
假设ABCDFG 已经访问，EH 还没访问，如果B位置最低， B也应忽略，因为 AFGD 就构
成边界了。
貌似很多这种情况，不知道如何有效分别出来。
就是说，若果弹出来的位置删除后，边界仍然完整，这个位置就直接 ignore.
【在 p*****2 的大作中提到】
: 写了一个。大家看看如果没什么问题。放到我的博客里去。
: http://blog.sina.com.cn/s/blog_b9285de20101j9a7.html
|
g*******s
发帖数: 2963 | 62 这题我曾经想了好久，试了好多方法，最后还是用了peking2（leetcode1337）的那个
。Orz一下 |
z*******3
发帖数: 13709 | 63 没认真看代码，不过光看描述
是不是有一个小问题？
如果这样做的话，是不是假设只有一个装水的点？
比如
33333
30313
33333
这种其实可以装3＋2＝5unit的水
但是如果只从0那个点装水并找周边的边界的话
会忽略掉1那个装水点
所以第一步是不是先把所有相对低点给找出来
然后挨个弹出来，再寻找最低边界在哪里
同时储存所有遍历过的点
最后用最低边界高度来减去每一个遍历过的点计算units
【在 p*****2 的大作中提到】
:
: 嗯。
|
z*******3
发帖数: 13709 | 64 想了下
先随机找一个点，然后往下流，一直流到一个低点，然后从这个低点根据二爷那个方法
计算储量
然后看是否走遍全部matrix，如果没有，继续再在未访问过的地方随机找一个点
然后往下流，流到一个低点，然后计算储量
直到所有的点都被访问 |
c*******3
发帖数: 28 | |
