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个方向
|
|