D****6
发帖数: 278 | 1 之前在版上看到的。
Given a matrix which contains black and white grids, use a method to find
out if the white grids are connected or not, if yes, return true.
这题是不是就是类似garbage collection mark and sweep. DFS就行了吧。 还有什么
高级做法吗？ | L***Q
发帖数: 508 | 2 如果可以改动matrix的值，有一个简单办法。
Idea: 如果所有white的cell相连，那么从任何一个white cell开始，往四个方向扩展
，把遇到的white都改成black，那么最终所有cell都是black。
step 1：find any white cell as start point;
step 2: use a queue or stack to record white cells: get a cell, set it as
black, and then check the four directions. If a neighbor is white, put it in
queue/stack; Finish when queue/stack is empty
step 3: check the board again, return false if finding a white cell.
Complexity O(n^2). 如果两个white cell (i, j)和(i+1, j+1)算是相连，那step 2就
是check 8个方向
【在 D****6 的大作中提到】
: 之前在版上看到的。
: Given a matrix which contains black and white grids, use a method to find
: out if the white grids are connected or not, if yes, return true.
: 这题是不是就是类似garbage collection mark and sweep. DFS就行了吧。 还有什么
: 高级做法吗？
| c**e
发帖数: 298 | 3 都连的条件是最多只有两个白点，它们的周围只有一个白点。遍历所有节点，每次检查
4个相连的点。
不知有没有更好的。
【在 D****6 的大作中提到】
: 之前在版上看到的。
: Given a matrix which contains black and white grids, use a method to find
: out if the white grids are connected or not, if yes, return true.
: 这题是不是就是类似garbage collection mark and sweep. DFS就行了吧。 还有什么
: 高级做法吗？
| D****6
发帖数: 278 | 4 想了想这题怎么都要走一遍。mark and sweep最容易了。 | c******a
发帖数: 789 | 5 不改原board也可以啊。
1. 从任一个白点开始，用你的queue走，走到走不动，看看总共搞过几个白点
2. check board，看一共有几个白点
看看1和2的白点数是不是一样。
in
【在 L***Q 的大作中提到】
: 如果可以改动matrix的值，有一个简单办法。
: Idea: 如果所有white的cell相连，那么从任何一个white cell开始，往四个方向扩展
: ，把遇到的white都改成black，那么最终所有cell都是black。
: step 1：find any white cell as start point;
: step 2: use a queue or stack to record white cells: get a cell, set it as
: black, and then check the four directions. If a neighbor is white, put it in
: queue/stack; Finish when queue/stack is empty
: step 3: check the board again, return false if finding a white cell.
: Complexity O(n^2). 如果两个white cell (i, j)和(i+1, j+1)算是相连，那step 2就
: 是check 8个方向
|
|
