如何在阵列上使用DFS [英] How to use DFS on an array

问题描述

我有一个一维值列表，它看起来像"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 to false
• Go through each point in two nested loops
• For each point where visited[r][c] is false, 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屋！