q******8
发帖数: 848 | 1 上来先是说了说简历。然后直入主题，写出fibonacci两种实现，给出复杂度。瞬间完
事。然后出了道算法。给一个matrix，每个element给的值代表高度。问这个matrix能
撑多少水。给出算法。不要求程序实现。比如3×3的矩阵，最外一圈都是3，然后中间
一个元素是0，那么这个矩阵可以撑3个单位的水。 |
d**e
发帖数: 6098 | 2 "撑多少水" 是什么意思？
【在 q******8 的大作中提到】
: 上来先是说了说简历。然后直入主题，写出fibonacci两种实现，给出复杂度。瞬间完
: 事。然后出了道算法。给一个matrix，每个element给的值代表高度。问这个matrix能
: 撑多少水。给出算法。不要求程序实现。比如3×3的矩阵，最外一圈都是3，然后中间
: 一个元素是0，那么这个矩阵可以撑3个单位的水。
|
q******8
发帖数: 848 | 3 能装多少水，比如一个3×3的矩阵，周围一圈元素的值都是5，中心那个元素的值是0，
那么这个矩阵能装5个单位的水。问任意矩阵怎么算？ |
t*****j
发帖数: 1105 | 4 周围一圈元素的最小值 - 中心元素的值 ?
【在 q******8 的大作中提到】
: 能装多少水，比如一个3×3的矩阵，周围一圈元素的值都是5，中心那个元素的值是0，
: 那么这个矩阵能装5个单位的水。问任意矩阵怎么算？
|
D***h
发帖数: 183 | 5 显然不是.可以装2.
2220
2020
2222
【在 t*****j 的大作中提到】
: 周围一圈元素的最小值 - 中心元素的值 ?
|
D***h
发帖数: 183 | 6 假定
050
505
050
算0，还是5？ 也就是要由4方，还是8方确定？
【在 q******8 的大作中提到】
: 能装多少水，比如一个3×3的矩阵，周围一圈元素的值都是5，中心那个元素的值是0，
: 那么这个矩阵能装5个单位的水。问任意矩阵怎么算？
|
d**e
发帖数: 6098 | 7 请问一个单位的水是指什么？
相当立方体? 1x1 是一个单位？
【在 D***h 的大作中提到】
: 显然不是.可以装2.
: 2220
: 2020
: 2222
|
q******8
发帖数: 848 | |
D***h
发帖数: 183 | 9 底座1x1,矩阵元素值表示高度吧
【在 d**e 的大作中提到】
: 请问一个单位的水是指什么？
: 相当立方体? 1x1 是一个单位？
|
q******8
发帖数: 848 | 10 元素值表示高度
【在 D***h 的大作中提到】
: 底座1x1,矩阵元素值表示高度吧
|
|
|
d**e
发帖数: 6098 | 11 不好意思，我还是有点看不懂 :(
你前面的例子 3x3矩阵，外围全是3，中间是零，如何算出是3个单位？
不是应该 8 * 3 = 24吗？
外围全是5时，不是 8 * 5 = 40 ?
【在 q******8 的大作中提到】
: 元素值表示高度
|
z****n
发帖数: 1379 | 12 竖过来看，周围一圈都是高是3的柱子，中间薄薄一层底子，高度是0，可不就是装
3个单位的水吗。数字代表的是筒壁的高度，是不能装水的东西的高度，中间空的部
分是能装水的
【在 d**e 的大作中提到】
: 不好意思，我还是有点看不懂 :(
: 你前面的例子 3x3矩阵，外围全是3，中间是零，如何算出是3个单位？
: 不是应该 8 * 3 = 24吗？
: 外围全是5时，不是 8 * 5 = 40 ?
|
d**e
发帖数: 6098 | 13 明白了。谢谢。
我还以为是反过来，外面一圈才是装水的。
【在 z****n 的大作中提到】
: 竖过来看，周围一圈都是高是3的柱子，中间薄薄一层底子，高度是0，可不就是装
: 3个单位的水吗。数字代表的是筒壁的高度，是不能装水的东西的高度，中间空的部
: 分是能装水的
|
a****n
发帖数: 1887 | |
s******c
发帖数: 932 | |
K******g
发帖数: 1870 | |
n******n
发帖数: 12088 | 17 周围一圈包括对角线否？
【在 z****n 的大作中提到】
: 竖过来看，周围一圈都是高是3的柱子，中间薄薄一层底子，高度是0，可不就是装
: 3个单位的水吗。数字代表的是筒壁的高度，是不能装水的东西的高度，中间空的部
: 分是能装水的
|
c***y
发帖数: 560 | 18 这个积水问题有答案吗？谢谢
谁贴一个, seems dynamic programming is OK, but hard to code out. Thanks.
for example:
3 6 7 8 9
5 3 1 2 6
6 3 0 2 5
4 2 3 3 2
The water should be (3-1) + (3-0) + (3-2) + (3-2) = 7. Very tough question.
【在 q******8 的大作中提到】
: 上来先是说了说简历。然后直入主题，写出fibonacci两种实现，给出复杂度。瞬间完
: 事。然后出了道算法。给一个matrix，每个element给的值代表高度。问这个matrix能
: 撑多少水。给出算法。不要求程序实现。比如3×3的矩阵，最外一圈都是3，然后中间
: 一个元素是0，那么这个矩阵可以撑3个单位的水。
|
d*******l
发帖数: 338 | 19 算法艺术与信息学竞赛（刘汝佳、黄亮）
【在 s******c 的大作中提到】
: 不知楼上这是那本书呢？
|
c***y
发帖数: 560 | 20 能够解释这道题的具体解法吗？谢谢
【在 d*******l 的大作中提到】
: 算法艺术与信息学竞赛（刘汝佳、黄亮）
|
|
|
d*******l
发帖数: 338 | 21 看了下应该能！只是讲的比较简略，上面图里的那些解释就是全部了
【在 c***y 的大作中提到】
: 能够解释这道题的具体解法吗？谢谢
|
c***y
发帖数: 560 | 22 my feeling is that it's hard to answer that problem with the solution,
Correct me if anybody here can explain the details. thanks.
【在 d*******l 的大作中提到】
: 看了下应该能！只是讲的比较简略，上面图里的那些解释就是全部了
|
h*********n
发帖数: 11319 | 23 find the point(s) with the lowest waterline
if we find k points with the same lowest waterline, we pour in k units of
water, so that the water level will rise only 1 unit.
repeat
i think the trick is in judging whether a few continuous grids are connected
to an edge grid
【在 c***y 的大作中提到】
: my feeling is that it's hard to answer that problem with the solution,
: Correct me if anybody here can explain the details. thanks.
|
c***y
发帖数: 560 | 24 see my example above, this solution does not work
【在 h*********n 的大作中提到】
: find the point(s) with the lowest waterline
: if we find k points with the same lowest waterline, we pour in k units of
: water, so that the water level will rise only 1 unit.
: repeat
: i think the trick is in judging whether a few continuous grids are connected
: to an edge grid
|
r********t
发帖数: 395 | 25
【在 q******8 的大作中提到】
: 上来先是说了说简历。然后直入主题，写出fibonacci两种实现，给出复杂度。瞬间完
: 事。然后出了道算法。给一个matrix，每个element给的值代表高度。问这个matrix能
: 撑多少水。给出算法。不要求程序实现。比如3×3的矩阵，最外一圈都是3，然后中间
: 一个元素是0，那么这个矩阵可以撑3个单位的水。
|
d*******l
发帖数: 338 | 26 我觉得那个解答非常有道理啊。每次找当前禁止注水的格子中高度最小的进行
floodfill，更新“禁止注水”格子的集合，直到所有格子都禁止注水。“禁止注水”
格子相当于桶的边界，从桶的边界的最低点开始注水，逐步缩小剩下的范围，想法很巧
妙。
你的例子举的不错，但上面的解法应该能正常工作，因为假设每次取的格子高度是h，
高度小于等于h的且能通过floodfill达到的范围内，周围的一圈格子都会被放进“禁止
注水”集合。用你的例子来说明，开始的时候禁止注水的是最外一圈，然后假设选出的
高度最小的用“*”表示：
1. 没有新的“禁止注水”格子被加入
. . . . .
. 3 1 2 .
. 3 0 2 .
. . . . * |
h*********n
发帖数: 11319 | 27 I think your idea is exactly like the idea from the book.
Key is always start from lowest edge grid->fill water from the edge grid to
the same height as the edge grid itself -> desert all flooded grids-->find t
he new lowest edge grid.
this way we can avoid the complicated judgement of whether a grid will spill
to the edge when water level rise.
【在 d*******l 的大作中提到】
: 我觉得那个解答非常有道理啊。每次找当前禁止注水的格子中高度最小的进行
: floodfill，更新“禁止注水”格子的集合，直到所有格子都禁止注水。“禁止注水”
: 格子相当于桶的边界，从桶的边界的最低点开始注水，逐步缩小剩下的范围，想法很巧
: 妙。
: 你的例子举的不错，但上面的解法应该能正常工作，因为假设每次取的格子高度是h，
: 高度小于等于h的且能通过floodfill达到的范围内，周围的一圈格子都会被放进“禁止
: 注水”集合。用你的例子来说明，开始的时候禁止注水的是最外一圈，然后假设选出的
: 高度最小的用“*”表示：
: 1. 没有新的“禁止注水”格子被加入
: . . . . .
|
h*********n
发帖数: 11319 | 28 3 6 7 8 9
5 3 1 2 6
6 3 0 2 5
4 2 3 3 2
3 6 7 8 9
5 3 1 2 6
6 3 0 2 5
4 2 3 3 *
3 6 7 8 9
5 3 1 2 6
6 3 0 2 5
4 * 3 3 *
* 6 7 8 9
5 3 1 2 6
6 3 0 2 5
4 * 3 3 *
* 6 7 8 9
5 3 * * 6
6 3 * * 5
4 * * * * 只有这一步灌进去7的水
【在 c***y 的大作中提到】
: 这个积水问题有答案吗？谢谢
: 谁贴一个, seems dynamic programming is OK, but hard to code out. Thanks.
: for example:
: 3 6 7 8 9
: 5 3 1 2 6
: 6 3 0 2 5
: 4 2 3 3 2
: The water should be (3-1) + (3-0) + (3-2) + (3-2) = 7. Very tough question.
|
d*******l
发帖数: 338 | 29 我就是在阐释我对那个解法的理解。。。
to
t
spill
【在 h*********n 的大作中提到】
: I think your idea is exactly like the idea from the book.
: Key is always start from lowest edge grid->fill water from the edge grid to
: the same height as the edge grid itself -> desert all flooded grids-->find t
: he new lowest edge grid.
: this way we can avoid the complicated judgement of whether a grid will spill
: to the edge when water level rise.
|
g******0
发帖数: 221 | 30 why can't we find the boundary first, then take the lowest cell h in the
boundary. For every interior cell, we know it can be filled up to h. It
seems much simpler this way... or did I miss something? |
