x****3
发帖数: 62 | 1 continental divider
给一个矩阵，其中0代表海洋，其他数字代表高度，秉着水往低处流的原则，求出能够
流向任意海洋的点。 比如说
0 0 0 1 2 3 0
0 1 2 2 4 3 2
2 1 1 3 3 2 0
0 3 3 3 2 3 3
那么就要给出 第二行的4 （这有这点出发，能够找到连通道四个0的区域的一条非递增
路线），当然也有可能找不到这样的点，或者找到多个点。 |
x*******6
发帖数: 262 | |
S*****a
发帖数: 5 | 3 对每个点，把比它小的改成零，比它大的当成山。如果能到每个零，这个点就是一个解。
行吗？
【在 x****3 的大作中提到】
: continental divider
: 给一个矩阵，其中0代表海洋，其他数字代表高度，秉着水往低处流的原则，求出能够
: 流向任意海洋的点。 比如说
: 0 0 0 1 2 3 0
: 0 1 2 2 4 3 2
: 2 1 1 3 3 2 0
: 0 3 3 3 2 3 3
: 那么就要给出 第二行的4 （这有这点出发，能够找到连通道四个0的区域的一条非递增
: 路线），当然也有可能找不到这样的点，或者找到多个点。
|
y****e
发帖数: 25 | 4 这个时间复杂度至少O(N^4)吧？
解。
【在 S*****a 的大作中提到】
: 对每个点，把比它小的改成零，比它大的当成山。如果能到每个零，这个点就是一个解。
: 行吗？
|
s****a
发帖数: 794 | 5 首先想到的是从每一个海洋往外做BFS，找所有可能的来源留下记号。最后的结果应该
是找到一个留下了各个海洋的记号的那些点就是了。这样做的复杂度应该是O(kn^2),k
是海洋的个数。很显然这个不是最优解，因为有很多陆地的地方被做了几遍BFS，很浪
费。所以面试时候应该边写着这个算法边考虑能不能每个点只往外做一次BFS呢？
一种想法是第一次走的时候把以后BFS的结果都记录下来。但是好像没什么用。另一种
想法是这个点做BFS的时候已经知道了能往哪些个海洋里流。这个看起来靠谱。顺着想
也就是说当一个陆地上的点已经被标注的次数和他周围下坡的次数相等的时候才在这个
点做BFS。
流程大约是：
先扫一遍所有的海洋（0），把同一个海洋里的所有点标上同一个数。
建一个队列Q，队列里加上所有的海洋点。
LOOP:对队列里的第一个点做一层BFS,也就是找他的“上坡或平路”邻居，都标上和自
己相同的数（有可能自己已经被标了好几次，要都标上）。
对所有的邻居检查是否符合上文的展开BFS的条件（标注个数==周围下坡数）如果符合
就推到Q里面去。
一直做这个loop直到Q空了。扫一遍所有点看哪个点被标了所有的海洋标号。
如果平路能流 可能出现循环的依赖 可能需要再检查下平路。
这种做法的复杂度应该是O(n^2)吧。
上面是个初步的想法，欢迎讨论。
改正，加入q的条件是这个点已经被到达的次数等于了周围下坡的邻居数 |
p******e
发帖数: 14 | |
y****e
发帖数: 25 | 7 海洋数最坏可能为O(N^2).
下坡数最多是四吧？
k
【在 s****a 的大作中提到】
: 首先想到的是从每一个海洋往外做BFS，找所有可能的来源留下记号。最后的结果应该
: 是找到一个留下了各个海洋的记号的那些点就是了。这样做的复杂度应该是O(kn^2),k
: 是海洋的个数。很显然这个不是最优解，因为有很多陆地的地方被做了几遍BFS，很浪
: 费。所以面试时候应该边写着这个算法边考虑能不能每个点只往外做一次BFS呢？
: 一种想法是第一次走的时候把以后BFS的结果都记录下来。但是好像没什么用。另一种
: 想法是这个点做BFS的时候已经知道了能往哪些个海洋里流。这个看起来靠谱。顺着想
: 也就是说当一个陆地上的点已经被标注的次数和他周围下坡的次数相等的时候才在这个
: 点做BFS。
: 流程大约是：
: 先扫一遍所有的海洋（0），把同一个海洋里的所有点标上同一个数。
|
n***z
发帖数: 29 | 8 不太懂，下坡数和标注个数或者海洋个数有什么关系？
我觉得每次每个海洋都bfs一层，然后可以用set/map合并下一步的点，
比如海洋1和海洋2这一层都bfs到一个点，可以标记为12，这样这个点以后bfs到的都标
记为12，表示可以到海洋1和2
k
【在 s****a 的大作中提到】
: 首先想到的是从每一个海洋往外做BFS，找所有可能的来源留下记号。最后的结果应该
: 是找到一个留下了各个海洋的记号的那些点就是了。这样做的复杂度应该是O(kn^2),k
: 是海洋的个数。很显然这个不是最优解，因为有很多陆地的地方被做了几遍BFS，很浪
: 费。所以面试时候应该边写着这个算法边考虑能不能每个点只往外做一次BFS呢？
: 一种想法是第一次走的时候把以后BFS的结果都记录下来。但是好像没什么用。另一种
: 想法是这个点做BFS的时候已经知道了能往哪些个海洋里流。这个看起来靠谱。顺着想
: 也就是说当一个陆地上的点已经被标注的次数和他周围下坡的次数相等的时候才在这个
: 点做BFS。
: 流程大约是：
: 先扫一遍所有的海洋（0），把同一个海洋里的所有点标上同一个数。
|
M**********7
发帖数: 378 | 9 好想法， 感觉是正解。
k
【在 s****a 的大作中提到】
: 首先想到的是从每一个海洋往外做BFS，找所有可能的来源留下记号。最后的结果应该
: 是找到一个留下了各个海洋的记号的那些点就是了。这样做的复杂度应该是O(kn^2),k
: 是海洋的个数。很显然这个不是最优解，因为有很多陆地的地方被做了几遍BFS，很浪
: 费。所以面试时候应该边写着这个算法边考虑能不能每个点只往外做一次BFS呢？
: 一种想法是第一次走的时候把以后BFS的结果都记录下来。但是好像没什么用。另一种
: 想法是这个点做BFS的时候已经知道了能往哪些个海洋里流。这个看起来靠谱。顺着想
: 也就是说当一个陆地上的点已经被标注的次数和他周围下坡的次数相等的时候才在这个
: 点做BFS。
: 流程大约是：
: 先扫一遍所有的海洋（0），把同一个海洋里的所有点标上同一个数。
|
h**********c
发帖数: 4120 | 10 Does it consider Caspian an ocean?
Or australian a continent?
In case of NPE |
|
|
M**********7
发帖数: 378 | 11 可以把入Q的条件改成：所有的平或低邻居都已经处理过么？可以利用count来做这个。
然后Q实际上变成一个以未处理低平邻居为key, key = 0, 1, 2, 3, 4的buckets。这样
避免大排序，每次O(1)
k
【在 s****a 的大作中提到】
: 首先想到的是从每一个海洋往外做BFS，找所有可能的来源留下记号。最后的结果应该
: 是找到一个留下了各个海洋的记号的那些点就是了。这样做的复杂度应该是O(kn^2),k
: 是海洋的个数。很显然这个不是最优解，因为有很多陆地的地方被做了几遍BFS，很浪
: 费。所以面试时候应该边写着这个算法边考虑能不能每个点只往外做一次BFS呢？
: 一种想法是第一次走的时候把以后BFS的结果都记录下来。但是好像没什么用。另一种
: 想法是这个点做BFS的时候已经知道了能往哪些个海洋里流。这个看起来靠谱。顺着想
: 也就是说当一个陆地上的点已经被标注的次数和他周围下坡的次数相等的时候才在这个
: 点做BFS。
: 流程大约是：
: 先扫一遍所有的海洋（0），把同一个海洋里的所有点标上同一个数。
|
M**********7
发帖数: 378 | 12 想法是一样的，只是这样的有个问题。
这个例子里面 最左边和最上的是位置标号。
假设1,2按照图示路径流，5次后，它们到[2,1]位置相遇，这时候因为2走快了，所以[3
,1] [3,2] [3,3]都需要更新。这样的情况极端的话会影响复杂度。
0 1 2 3 4 5
0 x x x x x x
1 x 1 1 1 1 1
2 2 2 x x x x
3 x 2 2 2 x x
下坡数和标注个数是为了让bfs按拓扑排序，让已经处理过的点已经包含所有能到达它
的海洋信息。
【在 n***z 的大作中提到】
: 不太懂，下坡数和标注个数或者海洋个数有什么关系？
: 我觉得每次每个海洋都bfs一层，然后可以用set/map合并下一步的点，
: 比如海洋1和海洋2这一层都bfs到一个点，可以标记为12，这样这个点以后bfs到的都标
: 记为12，表示可以到海洋1和2
:
: k
|
n***z
发帖数: 29 | 13 你的意思是等这个点所有可能的bfs都到齐了再继续bfs吧，比如你的例子里[2,1]开始
标2的时候先不bfs，等1到了再继续1的bfs。
但这样有可能碰到“死谷”吧，比如
3 3 3
3 1 3
0 2 4
这样2就一直再等1，不继续4吗？
[3
【在 M**********7 的大作中提到】
: 想法是一样的，只是这样的有个问题。
: 这个例子里面 最左边和最上的是位置标号。
: 假设1,2按照图示路径流，5次后，它们到[2,1]位置相遇，这时候因为2走快了，所以[3
: ,1] [3,2] [3,3]都需要更新。这样的情况极端的话会影响复杂度。
: 0 1 2 3 4 5
: 0 x x x x x x
: 1 x 1 1 1 1 1
: 2 2 2 x x x x
: 3 x 2 2 2 x x
: 下坡数和标注个数是为了让bfs按拓扑排序，让已经处理过的点已经包含所有能到达它
|
M**********7
发帖数: 378 | 14 漂亮的反例！：）
那看来第一轮除了海洋点之外，还要加入低（不能为平，否则还是死谷互锁）邻居数为
0的点，像死谷这种代表的是无海洋，当然也可以认为海洋点就是低邻居数为0的点。
处理平的情况还需要想想。
还有个想法，如果高度的数目有限，是不是可以按照高度入桶，从下向上淹，然后相当
于起点在不同海洋的小人(或无海洋)从不同路径向上躲，最后如果一个点把来自所有海洋
的小人凑齐了就算一个输出。
【在 n***z 的大作中提到】
: 你的意思是等这个点所有可能的bfs都到齐了再继续bfs吧，比如你的例子里[2,1]开始
: 标2的时候先不bfs，等1到了再继续1的bfs。
: 但这样有可能碰到“死谷”吧，比如
: 3 3 3
: 3 1 3
: 0 2 4
: 这样2就一直再等1，不继续4吗？
:
: [3
|
s****a
发帖数: 794 | 15 呃 我的回复点歪了。。。给你了短信。。。 麻烦你贴出来好么。。。
【在 n***z 的大作中提到】
: 你的意思是等这个点所有可能的bfs都到齐了再继续bfs吧，比如你的例子里[2,1]开始
: 标2的时候先不bfs，等1到了再继续1的bfs。
: 但这样有可能碰到“死谷”吧，比如
: 3 3 3
: 3 1 3
: 0 2 4
: 这样2就一直再等1，不继续4吗？
:
: [3
|
h****t
发帖数: 69 | 16 上面说从每一个海洋往外做BFS的我有点不太明白，象下面这种情况如何处理?
3 3 3 3 x 4
3 4 4 4 4 0
3 3 3 3 3 3
如 x=3 BFS如何断定x能够流到海洋？ |
n***z
发帖数: 29 | 17 ok
寄信人: shuiya (shuiya)
标 题: Re: 请教G家新题 continental divider
发信站: 未名空间 (Fri Feb 6 13:40:33 2015)
来 源: 131.
不好意思一直忙别的事。是会出现这种情况但也比较容易fix，就是在能扩展的点都做
完了之后，再做所有没做过BFS的。然后还是遵循Q里面有就先做Q里的，没有就弄没做
BFS的。这个对复杂度没有影响。
还有就是这种情况平路的话能循环的依赖，也是要平路的BFS一下。
3 3 3 3 3 3
3 0 3 3 0 3
3 3 3 3 3 3
但是不管怎么说都是保证每个点BFS一次。关键是做BFS的顺序
就是说复杂度也就是O(n^2)的不变。
我是真的觉得这种题对于我来说真的很难的面试了。我只能写出我帖子里说的第一种做
法，写代码的时候应该能想出这种优化的。但一个小时肯定不够我再写这种的和处理些
特殊情况。
【在 s****a 的大作中提到】
: 呃 我的回复点歪了。。。给你了短信。。。 麻烦你贴出来好么。。。
|
M**********7
发帖数: 378 | 18 从大家发的面经来看，好像海洋的定义一般是四个边缘，或者两个边缘等。
看你这个例子，你可能认为0是海洋。
不过bfs方法一样的。
从0点开始，如果周围比自身高，就代表可以从那个地方流到自己，然后把这个集合bfs。
或者如果把高度理解成深度，可以变成从0点可以流到的任何地方。
你的例子中
第一次0 可以流到3 4 4，
第二次 上面的4不能扩展，因为没有比它不大的邻居；左边的4可以继续向左扩展；下
面的3可以向左扩展。
这样持续BFS，第二次中左边的4扩展到你图中最左边的4就截止了
而3则可以辗转扩展到x左边的3。
如果x=3，经由x左边的3就可以扩到x。
当然如果x>=4从4就bfs到x了。
x<=2则不可能到x。
【在 h****t 的大作中提到】
: 上面说从每一个海洋往外做BFS的我有点不太明白，象下面这种情况如何处理?
: 3 3 3 3 x 4
: 3 4 4 4 4 0
: 3 3 3 3 3 3
: 如 x=3 BFS如何断定x能够流到海洋？
|
n***z
发帖数: 29 | 19 我觉得ls的方法可以解决死谷问题，就是按你说的比较访问次数和下坡次数，如果不同
，并不扔掉，只是放到queue后面去，这样等queue的size稳定的时候再忽略这个要求
pop出一个来，继续bfs，直到queue为空。
海洋
【在 M**********7 的大作中提到】
: 漂亮的反例！：）
: 那看来第一轮除了海洋点之外，还要加入低（不能为平，否则还是死谷互锁）邻居数为
: 0的点，像死谷这种代表的是无海洋，当然也可以认为海洋点就是低邻居数为0的点。
: 处理平的情况还需要想想。
: 还有个想法，如果高度的数目有限，是不是可以按照高度入桶，从下向上淹，然后相当
: 于起点在不同海洋的小人(或无海洋)从不同路径向上躲，最后如果一个点把来自所有海洋
: 的小人凑齐了就算一个输出。
|
M**********7
发帖数: 378 | 20 想了一下， 好像平路的不能简单的BFS。
举个例子，这里数字代表海洋，左边是海洋1，右边海洋2，所有路平路
1 1 1 1 1 1 1 2 2 2 2 2 2
相遇的时候不能只update相遇点，而是所有平路点要全部变成所有相关海洋的全集，就
要求把所有连通平路放一起处理。
所以如果说保证没有平的就太好了，这个如果真面要问一下可不可以没有平路。
【在 n***z 的大作中提到】
: ok
: 寄信人: shuiya (shuiya)
: 标 题: Re: 请教G家新题 continental divider
: 发信站: 未名空间 (Fri Feb 6 13:40:33 2015)
: 来 源: 131.
: 不好意思一直忙别的事。是会出现这种情况但也比较容易fix，就是在能扩展的点都做
: 完了之后，再做所有没做过BFS的。然后还是遵循Q里面有就先做Q里的，没有就弄没做
: BFS的。这个对复杂度没有影响。
: 还有就是这种情况平路的话能循环的依赖，也是要平路的BFS一下。
: 3 3 3 3 3 3
|
|
|
M**********7
发帖数: 378 | 21 我总觉得放到Q后面重新排队会影响复杂度。
还是哪里没想到？
【在 n***z 的大作中提到】
: 我觉得ls的方法可以解决死谷问题，就是按你说的比较访问次数和下坡次数，如果不同
: ，并不扔掉，只是放到queue后面去，这样等queue的size稳定的时候再忽略这个要求
: pop出一个来，继续bfs，直到queue为空。
:
: 海洋
|
s******d
发帖数: 9806 | 22 大致的思路：
1.海洋的定义：4条边之外的地方定义为海洋。四个角可以认为同时联通两片海洋。0的
地方可以认为是海洋的延伸（如果与某些边相连）。
2.数据结构的设计：需要存储一个矩阵X，每个点需要4个bit，分别存储其是否与四片
海洋连接。若四个bit都被置为1，则输出此点。另需一个bit表示该点是否已在搜索队
列内待搜索。
3.初始值设置：四条边根据其所在位置，设置相应的bit，四个角设置两个bit。
4.搜索策略：从某条边的全部点入队，BFS搜索相邻点。遇到值大于等于当前点，则设
置X对应bit，若此点当前不在队列内，进队列。否则终止搜索。（这里有个小问题，就
是平地算不算可以流水，例如:1224,如果不算的话，要修改判断条件）
5. 针对每条边BFS搜索一次。最后输出所有四个bit均被置为1的点。
这个BFS基本上还是可以保证O(n^2)的时间复杂度，因为每个点最多会被搜索4*8=32次。
【在 x****3 的大作中提到】
: continental divider
: 给一个矩阵，其中0代表海洋，其他数字代表高度，秉着水往低处流的原则，求出能够
: 流向任意海洋的点。 比如说
: 0 0 0 1 2 3 0
: 0 1 2 2 4 3 2
: 2 1 1 3 3 2 0
: 0 3 3 3 2 3 3
: 那么就要给出 第二行的4 （这有这点出发，能够找到连通道四个0的区域的一条非递增
: 路线），当然也有可能找不到这样的点，或者找到多个点。
|
h**********c
发帖数: 4120 | 23 怎么也要先把0扫一遍吧，
要不Target(TM)那种结构就NPE了吧！ |
n***z
发帖数: 29 | 24 那就用一个set/map存呢？
【在 M**********7 的大作中提到】
: 我总觉得放到Q后面重新排队会影响复杂度。
: 还是哪里没想到？
|
M**********7
发帖数: 378 | 25 真的要处理平路的情况的话，有几个地方：
1. 每次处理点的时候分两步：
第一步bfs找到所有连通平路，然后update所有点的海洋集合。update所有未处理
邻居的未处理更低点的数目，把这些邻居放到应放的桶里面。
第二步再处理其他点。
或者说处理的时候连通平路要一起处理。
2. 对于每个以按未处理更低点数目的桶，内部再分两桶：需要优先处理的有更高未处
理邻居的桶，和一个没有更高未处理邻居的桶。这是为了对付这种情况：
数字为高度：
1 1 1 1 1 1
1 1 1 1 1 1
1 1 0 0 0 1
1 1 0 0 0 1
1 1 0 0 0 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
被1环绕的1的更低邻居数是0
而所有0的更低邻居数也是0
我们需要优先处理0
这个可以理解为按照高度排序，优先处理低的。
BTW 觉得这道题应该不会真考让处理平路的情况，应该有个思路就好了，因为那个本身
就是围棋求所有被围区域的题。当然了， 大牛不一样。
【在 M**********7 的大作中提到】
: 想了一下， 好像平路的不能简单的BFS。
: 举个例子，这里数字代表海洋，左边是海洋1，右边海洋2，所有路平路
: 1 1 1 1 1 1 1 2 2 2 2 2 2
: 相遇的时候不能只update相遇点，而是所有平路点要全部变成所有相关海洋的全集，就
: 要求把所有连通平路放一起处理。
: 所以如果说保证没有平的就太好了，这个如果真面要问一下可不可以没有平路。
|
M**********7
发帖数: 378 | 26 我觉得还需要有序，最好能知道下一个确定可以处理的点是哪个，不能拿一个，看看不
行再放回去，即使这样，也要限制这样做的步数为O(1)。
我一下子想不到用set/map的直接方法。
也许可以按照高度存map，然后在其中找连通的平路。
见我回的其他贴，这题的所有连通平路的确需要组团处理。
【在 n***z 的大作中提到】
: 那就用一个set/map存呢？
|
g****v
发帖数: 971 | 27 按照你这个定义， 4下面的那个3也可以是个solution了 which is not correct。
0 0 0 1 2 3 0
0 1 2 2 4 3 2
2 1 1 3 3 2 0
0 3 3 3 2 3 3
【在 s******d 的大作中提到】
: 大致的思路：
: 1.海洋的定义：4条边之外的地方定义为海洋。四个角可以认为同时联通两片海洋。0的
: 地方可以认为是海洋的延伸（如果与某些边相连）。
: 2.数据结构的设计：需要存储一个矩阵X，每个点需要4个bit，分别存储其是否与四片
: 海洋连接。若四个bit都被置为1，则输出此点。另需一个bit表示该点是否已在搜索队
: 列内待搜索。
: 3.初始值设置：四条边根据其所在位置，设置相应的bit，四个角设置两个bit。
: 4.搜索策略：从某条边的全部点入队，BFS搜索相邻点。遇到值大于等于当前点，则设
: 置X对应bit，若此点当前不在队列内，进队列。否则终止搜索。（这里有个小问题，就
: 是平地算不算可以流水，例如:1224,如果不算的话，要修改判断条件）
|
S*****a
发帖数: 5 | 28 手机写得大意。
对每个点做bfs,是NxN.不改成0直接做也行。想通了是个简单题。
返回ret
hashtable <, v> ht 记录所有0 cell
foreach cell (x,y)
队列 v
v.enque(cell)
while !v.empty()
if cell =0, map.erase(cell)
if map.empty()
ret.add (cell)
if cell > up, v.enque(up)
同理
down
left
right
【在 y****e 的大作中提到】
: 这个时间复杂度至少O(N^4)吧？
:
: 解。
|
z***y
发帖数: 73 | 29 首先将问题分解一下:
1.一个点是否能通向海洋?
2.一个点是否能通向邻居节点?
那么目标就是找到:
1.一个点可以通向他四个邻居节点,并且四个邻居节点都可以通向海洋.
大致解法就是:
1.首先建立一个矩阵保存状态,一个节点的状态有三种:
a.初始化,还没有处理过;b.可以通向海洋;c.不能通向海洋.
2.然后我们遍历原始矩阵:
2.1.如果当前节点值为0,那么设置此节点状态为b,同时设置此节点右和下邻居状态为b;
2.2.如果当前节点状态不为a,说明处理过,那么不用处理;
2.3.如果当前节点值不为0,且未处理过,循环查找邻居节点状态:
2.3.1如果当前邻居节点不可达,跳到下一个邻居节点;
2.3.2如果邻居节点可达:
2.3.2.1其状态为a,当前节点设置为该邻居节点,递归;
2.3.2.2其状态为b,当前节点状态为b,该节点处理完毕;
2.3.2.2其状态为c,跳到下一个邻居节点.
3.3所有邻居处理完毕,均为发现状态b,该节点状态为c;
3.从节点(1,1)开始遍历到节点(row - 2, column - 2)
1.当前节点大于0,并且可达所有邻居节点,并且所有邻居节点状态为b,将该节点加入结
果集合
第一遍循环要执行m*n此,第二遍(m-2)*(n-2).第一遍循环里面虽然有递归,但是每个节
点最多被处理一次,所以时间复杂度应该为O(m*n)，空间复杂度O(m*n) |
y****e
发帖数: 25 | 30 曾经见过另一道题，极其类似。只是仅有上下左右四片海。
天天想上，您这题没记错吧？
按照你的版本，最坏情况会有O(N^2)片海：
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
【在 x****3 的大作中提到】
: continental divider
: 给一个矩阵，其中0代表海洋，其他数字代表高度，秉着水往低处流的原则，求出能够
: 流向任意海洋的点。 比如说
: 0 0 0 1 2 3 0
: 0 1 2 2 4 3 2
: 2 1 1 3 3 2 0
: 0 3 3 3 2 3 3
: 那么就要给出 第二行的4 （这有这点出发，能够找到连通道四个0的区域的一条非递增
: 路线），当然也有可能找不到这样的点，或者找到多个点。
|
|
|
y****e
发帖数: 25 | 31 你把题改了，本题可能有O(N^2)片海。你这个版本只有上下左右四片海。
按四片海做的思路不错。我倾向于平地可以流水。
不需要4个bit，一个就够了，初始化为1，只要有一片海到不了就清零。
【在 s******d 的大作中提到】
: 大致的思路：
: 1.海洋的定义：4条边之外的地方定义为海洋。四个角可以认为同时联通两片海洋。0的
: 地方可以认为是海洋的延伸（如果与某些边相连）。
: 2.数据结构的设计：需要存储一个矩阵X，每个点需要4个bit，分别存储其是否与四片
: 海洋连接。若四个bit都被置为1，则输出此点。另需一个bit表示该点是否已在搜索队
: 列内待搜索。
: 3.初始值设置：四条边根据其所在位置，设置相应的bit，四个角设置两个bit。
: 4.搜索策略：从某条边的全部点入队，BFS搜索相邻点。遇到值大于等于当前点，则设
: 置X对应bit，若此点当前不在队列内，进队列。否则终止搜索。（这里有个小问题，就
: 是平地算不算可以流水，例如:1224,如果不算的话，要修改判断条件）
|
y****e
发帖数: 25 | 32 处理这个地图好像有问题：
1 1
1 0
为b;
【在 z***y 的大作中提到】
: 首先将问题分解一下:
: 1.一个点是否能通向海洋?
: 2.一个点是否能通向邻居节点?
: 那么目标就是找到:
: 1.一个点可以通向他四个邻居节点,并且四个邻居节点都可以通向海洋.
: 大致解法就是:
: 1.首先建立一个矩阵保存状态,一个节点的状态有三种:
: a.初始化,还没有处理过;b.可以通向海洋;c.不能通向海洋.
: 2.然后我们遍历原始矩阵:
: 2.1.如果当前节点值为0,那么设置此节点状态为b,同时设置此节点右和下邻居状态为b;
|
z***y
发帖数: 73 | 33 有啥问题？
产生的状态matrix是:
c b
b b
第二遍遍历从内层走，所以一次没运行，结果就是空
【在 y****e 的大作中提到】
: 处理这个地图好像有问题：
: 1 1
: 1 0
:
: 为b;
|
h**********c
发帖数: 4120 | 34 这个题其实我老再不谦虚一下，又刺激了某些人
我前组的一个老年，我老其实在评论自己的code，据称人家被气哆唆了，老黑拿枪比亮
我roommate，我都没眨一下。
其实想说这个题，其实流体力学里的有限元网格要比这个难的多，模型是真正的流体，
还要加粘性。
其实不是理论流体，是计算流体力学，finite element grid吧？
再吹一下niub,我前老板手下的博后搞的bordering algorithm，apply to this, 这个
也是小case。
不过一般计算讲收敛，精度，不讲polynomial，big O啥的。
没准狗家真有流力的博后，教授构思出来的
【在 x****3 的大作中提到】
: continental divider
: 给一个矩阵，其中0代表海洋，其他数字代表高度，秉着水往低处流的原则，求出能够
: 流向任意海洋的点。 比如说
: 0 0 0 1 2 3 0
: 0 1 2 2 4 3 2
: 2 1 1 3 3 2 0
: 0 3 3 3 2 3 3
: 那么就要给出 第二行的4 （这有这点出发，能够找到连通道四个0的区域的一条非递增
: 路线），当然也有可能找不到这样的点，或者找到多个点。
|
b****h
发帖数: 163 | 35 构造一个DAG，每个节点包括互相连通并且相同高度的所有点，link只能从高度低的点
指向高度高的
点，构造这个DAG需要遍历每个点并且用hashmap， 总共需要O（n^2）时间和空间。
然后这个DAG中从入度为0的node开始，分析每个node包括的海洋，可以分析一个从DAG
中把这个node删了，这样一直分析入度为0的node
总共需要O（n^2）时间和空间。 |
s****a
发帖数: 794 | 36 找到一个入度为0的点复杂度就要n^2了。。。
DAG
【在 b****h 的大作中提到】
: 构造一个DAG，每个节点包括互相连通并且相同高度的所有点，link只能从高度低的点
: 指向高度高的
: 点，构造这个DAG需要遍历每个点并且用hashmap， 总共需要O（n^2）时间和空间。
: 然后这个DAG中从入度为0的node开始，分析每个node包括的海洋，可以分析一个从DAG
: 中把这个node删了，这样一直分析入度为0的node
: 总共需要O（n^2）时间和空间。
|
b****h
发帖数: 163 | 37 是啊 所有入度为0的点进queue 然后处理过程中新入度为0的点不断加进去 这样总时间
和DAG 里link数目linear。 因为这个DAG必然是平面图 所以最后时间是n^2
【在 s****a 的大作中提到】
: 找到一个入度为0的点复杂度就要n^2了。。。
:
: DAG
|
b****h
发帖数: 163 | 38 其实我这个和你那个BFS优化本质上一样的 我这样处理相同高度的点比较容易。但我们
这2种方法都有一个问题没有考虑， 就是对每个点， 如何合并从比它低的所有点包含
的海洋。 直觉上用hashtable可能还会超过n^2
我回去再想想
【在 s****a 的大作中提到】
: 找到一个入度为0的点复杂度就要n^2了。。。
:
: DAG
|
h**********c
发帖数: 4120 | |
h**********c
发帖数: 4120 | 40 The nutshell of this thinking is any path is the homotopy of 0<->1 |
|
|
m*****k
发帖数: 731 | 41 O(kn^2),k
may I ask what is n?
if the matrix is n*m,
should be O(knm) 吧？
0 can be visited by other 0,
we can start BFS only with unvisited 0
k |
h**********c
发帖数: 4120 | 42 import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
/**
* This is a brain-tease. To find from array elements, monotone (less than
not equal) decreasing from adjacent element, leading to all '0's.
* Connected zeros is one ocean.
* The solution is growing the sea level, when all oceans become one BODY,
the none-basin (none-prohibited) element is the answer.
*/
//DONE Identify water bodies
//DONE Manually design other cases: trivial change
//TODO Handle basin : in StringData1 e.g. (3,4) = 2 is a basin. No water can
flow from it. So it is a not a flood-able element.
//TODO Automatically generate a map
public class ContinentalMap {
public static final int closed = 8848;
public static final String stringData1
= "0 0 0 1 2 3 0 \n"
+ "0 1 2 2 4 3 2 \n"
+ "2 1 1 3 3 2 0 \n"
+ "0 3 3 3 2 3 3";
public static final String stringData2
= "0 0 2 0\n"
+ " 0 1 1 3\n"
+ " 0 2 1 3\n"
+ " 1 2 3 3\n"
+ " 2 4 3 2\n"
+ " 3 3 2 3\n"
+ " 0 2 0 3";
protected int [][] data;
public static final int waterBodyLimit = 10000;
public int countOceans () {
// store
Map checkedWaterBodies = new LinkedHashMap
Integer> ();
// store
Map oceanPedia = new LinkedHashMap
();
// We come from north-west
for (int i = 0 ; i < data.length; i++) {
for (int j = 0; j
if ( 0 == data[i][j] ) {
// check west
if ( j-1 >=0 && data[i][j-1]==0 && checkedWaterBodies.
containsKey( i*waterBodyLimit + j-1)) {
int currentOceanId = checkedWaterBodies.get( i*
waterBodyLimit + j-1);
checkedWaterBodies.put(i*waterBodyLimit + j,
currentOceanId);
int newCount = oceanPedia.get(currentOceanId)+1;
oceanPedia.put(currentOceanId, newCount);
}
// check north
else if ( i-1>=0 && data[i-1][j]==0 &&
checkedWaterBodies.containsKey((i-1)*waterBodyLimit + j) ) {
int currentOceanId = checkedWaterBodies.get( (i-1)*
waterBodyLimit + j);
checkedWaterBodies.put(i*waterBodyLimit + j,
currentOceanId);
int newCount = oceanPedia.get(currentOceanId)+1;
oceanPedia.put(currentOceanId, newCount);
}
// none above is water, a new ocean discovered
else {
int newOceanId = oceanPedia.size()+1;
oceanPedia.put(newOceanId, 1);
checkedWaterBodies.put(i*waterBodyLimit + j,
newOceanId);
}
}
}
}
return oceanPedia.size();
}
public ContinentalMap(String input) {
String [] rows = input.trim().split("\n");
int totalRows = rows.length;
data = new int [totalRows][];
int i = 0;
for ( String row : rows) {
String [] elements = row.trim().split("\s+");
data[i] = new int [elements.length];
for (int j = 0; j
data[i][j] = Integer.parseInt(elements[j]);
}
i++;
}
}
public void flood () {
for (int i = 0 ; i < data.length; i++) {
for (int j = 0; j
if ( data[i][j] > 0)
data[i][j] -= 1;
}
}
}
public void printData () {
if (null == data)
return;
String stringData = "";
for (int i = 0 ; i < data.length; i++) {
String row = "";
for (int j = 0; j
row += data[i][j] + " ";
}
stringData += row.trim()+"\n";
}
System.out.println(stringData);
}
public boolean checkFloodedCondition () {
boolean result = true;
loop1 : for (int i = 0 ; i < data.length; i++) {
loop2 : for (int j = 0; j
if (data[i][j] != 0) {
result = false;
break loop1;
}
}
}
return result;
}
public void showResult () {
loop1 : for (int i = 0 ; i < data.length; i++) {
loop2 : for (int j = 0; j
if (data[i][j] != 0 && data[i][j]!= closed) {
System.out.printf("Element at (%d,%d) \n",i,j);
}
}
}
}
public static void main(String[] args) {
System.out.println("Test case I");
// Init a map
ContinentalMap continentalMap = new ContinentalMap(stringData1 );
// Print map
while (!continentalMap.checkFloodedCondition()) {
int oceansCount = continentalMap.countOceans ();
System.out.println("Oceans count = " +oceansCount);
if (oceansCount == 1) {
continentalMap.showResult();
}
continentalMap.printData();
continentalMap.flood();
}
System.out.println("Test case II");
// Init a map
continentalMap = new ContinentalMap(stringData2 );
// Print map
while (!continentalMap.checkFloodedCondition()) {
int oceansCount = continentalMap.countOceans ();
System.out.println("Oceans count = " +oceansCount);
if (oceansCount == 1) {
continentalMap.showResult();
}
continentalMap.printData();
continentalMap.flood();
}
}
} |
h**********c
发帖数: 4120 | 43 简单写了一下
用 java，思路是flooding
按照楼主原文4是答案，所以不能平移
我英文注释说，growing sea level, when oceans become one body， any elements
adjacent to water ( not checked in the above) are the answers.
对于basin，水出不去的地方，思路有，flood 到的时候，设成无限高（closed).
这题折腾不知道有什么意义没有，有什么数学或图形学上的理论吗？或者在计算机图形
图象上有什么应用？
所以不想花更多时间
上贴还有TODO没有完工。
大家愿加test case非常欢迎
也可以直接拉我github 上code
【在 x****3 的大作中提到】
: continental divider
: 给一个矩阵，其中0代表海洋，其他数字代表高度，秉着水往低处流的原则，求出能够
: 流向任意海洋的点。 比如说
: 0 0 0 1 2 3 0
: 0 1 2 2 4 3 2
: 2 1 1 3 3 2 0
: 0 3 3 3 2 3 3
: 那么就要给出 第二行的4 （这有这点出发，能够找到连通道四个0的区域的一条非递增
: 路线），当然也有可能找不到这样的点，或者找到多个点。
|
x*******9
发帖数: 138 | 44 #include
#include
#include
#include
#include
#include
using namespace std;
#define input(x) cin >> x
#define print(x) cout << x << endl
const int SIZE = 512;
const int mx[] = {0, 1, 0, -1};
const int my[] = {-1, 0, 1, 0};
int n, sea_cnt;
char g[SIZE][SIZE];
int nr[SIZE][SIZE];
int cnc[SIZE][SIZE];
void find_sea(int y, int x) {
if (g[y][x] != '0') {
return;
}
nr[y][x] = sea_cnt;
for (int i = 0; i < 4; i++) {
int ny = y + my[i];
int nx = x + mx[i];
if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
find_sea(ny, nx);
}
}
}
int dfs(int y, int x) {
if (cnc[y][x] != -1) {
return cnc[y][x];
}
cnc[y][x] = 0;
// if this node is a part of a sea
if (nr[y][x] != -1) {
cnc[y][x] |= (1 << nr[y][x]);
return cnc[y][x];
}
for (int i = 0; i < 4; i++) {
int ny = y + my[i];
int nx = x + mx[i];
if (ny >= 0 && ny < n && nx >= 0 && nx < n && g[y][x] > g[ny][nx]) {
cnc[y][x] |= dfs(ny, nx);
}
}
return cnc[y][x];
}
int main() {
sea_cnt = 0;
input(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int u;
scanf("%d", &u);
g[i][j] = u + '0';
}
}
memset(nr, -1, sizeof(nr));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] != '0' || nr[i][j] != -1) {
continue;
}
find_sea(i, j);
sea_cnt++;
}
}
memset(cnc, -1, sizeof(cnc));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (cnc[i][j] != -1) {
continue;
}
dfs(i, j);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (cnc[i][j] == (1 << sea_cnt) -1) {
printf("<%d, %d>\n", i, j);
}
}
}
return 0;
}
抛砖引玉，时间复杂度O(n ** 2)
代码有地方比较烂。。。求轻拍 |
h**********c
发帖数: 4120 | 45 Can you use stringstream parse the input, so we don't have to input the data
manually?
And make the data a char array in the scope.
So we just copy peest it and compile run.
Thanks,
【在 x*******9 的大作中提到】
: #include
: #include
: #include
: #include
: #include
: #include
: using namespace std;
: #define input(x) cin >> x
: #define print(x) cout << x << endl
: const int SIZE = 512;
|
M**********7
发帖数: 378 | 46 One body的想法很赞!
【在 h**********c 的大作中提到】
: import java.util.ArrayList;
: import java.util.LinkedHashMap;
: import java.util.List;
: import java.util.Map;
: /**
: * This is a brain-tease. To find from array elements, monotone (less than
: not equal) decreasing from adjacent element, leading to all '0's.
: * Connected zeros is one ocean.
: * The solution is growing the sea level, when all oceans become one BODY,
: the none-basin (none-prohibited) element is the answer.
|
h**********c
发帖数: 4120 | 47 there is bug just figure out, you insert a 5 randomly :(
【在 M**********7 的大作中提到】
: One body的想法很赞!
|
b***e
发帖数: 1419 | 48 This is still O(k*n^2), because you have O(n^2) cells each of which hold O(k
) marks.
k
【在 s****a 的大作中提到】
: 首先想到的是从每一个海洋往外做BFS，找所有可能的来源留下记号。最后的结果应该
: 是找到一个留下了各个海洋的记号的那些点就是了。这样做的复杂度应该是O(kn^2),k
: 是海洋的个数。很显然这个不是最优解，因为有很多陆地的地方被做了几遍BFS，很浪
: 费。所以面试时候应该边写着这个算法边考虑能不能每个点只往外做一次BFS呢？
: 一种想法是第一次走的时候把以后BFS的结果都记录下来。但是好像没什么用。另一种
: 想法是这个点做BFS的时候已经知道了能往哪些个海洋里流。这个看起来靠谱。顺着想
: 也就是说当一个陆地上的点已经被标注的次数和他周围下坡的次数相等的时候才在这个
: 点做BFS。
: 流程大约是：
: 先扫一遍所有的海洋（0），把同一个海洋里的所有点标上同一个数。
|
c****r
发帖数: 129 | 49 m
【在 x****3 的大作中提到】
: continental divider
: 给一个矩阵，其中0代表海洋，其他数字代表高度，秉着水往低处流的原则，求出能够
: 流向任意海洋的点。 比如说
: 0 0 0 1 2 3 0
: 0 1 2 2 4 3 2
: 2 1 1 3 3 2 0
: 0 3 3 3 2 3 3
: 那么就要给出 第二行的4 （这有这点出发，能够找到连通道四个0的区域的一条非递增
: 路线），当然也有可能找不到这样的点，或者找到多个点。
|
h**********c
发帖数: 4120 | 50 把我的答案贴一下
https://github.com/wangzhikai/PassFunder
运行 main in IdentifyContinuousBody.java
答案在test 8输出，按楼主数据，输出＇４＇的位置
思路在文件头comment
较长，谨慎入
欢迎找bug，design more test cases
觉得这个可以搞一个javascript或者其它UI 的sudoku游戏，欢迎加盟。
讨论请限于本题相关，
thanks for you time |
|
|
x*******9
发帖数: 138 | 51
data
As the input is like:
'''
0 0 0 1 2 3 0
0 1 2 2 4 3 2
2 1 1 3 3 2 0
0 3 3 3 2 3 3
'''
Read integers from stdin is a better choice here.
(I'm lazy! :))
【在 h**********c 的大作中提到】
: Can you use stringstream parse the input, so we don't have to input the data
: manually?
: And make the data a char array in the scope.
: So we just copy peest it and compile run.
: Thanks,
|
