如何在阵列上使用DFS [英] How to use DFS on an array
本文介绍了如何在阵列上使用DFS的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我有一个一维值列表,它看起来像"int [] values'".我相信我已经将其转换为这样的2d列表:
I have a 1 dimensional list of values, it looks like this "int[] values'". I beleive I have converted it to a 2d list like this :
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
board[i][j] = values[i * 4 + j];
}
}
木板是新的二维值列表.板上有数字. 0表示空白,a 1表示绿色,a 2表示蓝色,a 3表示红色.我该如何使用深度优先搜索来找到某种颜色的完整路径?
The board is the new 2 dimensional list of values. On the board there are numbers. A 0 means an empty space, a 1 is a green, a 2 is a blue, and a 3 is a red. How would I use depth first search to find a completed path of a certain color?
推荐答案
- 制作2D数组
boolean[][] visited
,指定您访问过的点;将所有元素设置为false
- 在两个嵌套循环中遍历每个点
- 对于
visited[r][c]
为false
的每个点,进入一个DFS,您可以递归实现 - 在递归DFS调用中检查该点是否是您的目的地;如果是,则返回
true
- 如果该点具有正确的颜色,请在四个方向上探索其相邻点(最多四个)
- 如果邻居的颜色正确,请将其标记为已访问,然后进行递归调用
- 如果递归调用返回
true
,则返回true - 否则,继续探索其他邻居
- 完成对邻居的探索后,返回
false
. - Make a 2D array
boolean[][] visited
designating the points that you have visited; set all elements tofalse
- Go through each point in two nested loops
- For each point where
visited[r][c]
isfalse
, go into a DFS which you can implement recursively - Inside the recursive DFS call check if the point is your destination; if yes, return
true
- If the point has the correct color, explore its neighbors (up to four) in four directions
- If a neighbor has the right color, mark it as visited, and make a recursive call
- If a recursive call returns
true
, return true - Otherwise, continue exploring other neighbors
- Once you are done exploring neighbors, return
false
.
这篇关于如何在阵列上使用DFS的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文