DFS 方法未产生预期输出

Question

所以目标是使用 dfs 打印所有可能的数字，这些数字的数字可以由棋盘上的一系列相邻字符组成。相邻我的意思是彼此相邻，垂直，水平或对角线。总共有 8 个运动方向。例如：下面的板

1 2
3 4

为了简单起见，假设我们总是必须从 row0 column0 开始，也就是 1。所以可能的数字是：1, 12, 13, 14, 123, 124, 132, 134, 142, 143 , 1234 等（这种情况非常简单，因为所有数字都直接相邻）所以我有以下代码：

static char[][] grid;
static int rows;
static int columns;

public static void main(String[] args) {
    //test grid. made it small so that solutions are easy to count
    grid = new char[][]{
            new char[]{'1', '2'},
            new char[]{'3', '4'},
    };
    rows = grid.length;
    columns = grid[0].length;
    dfs(0, 0, new boolean[rows][columns], new StringBuilder());
}

public static void dfs(int row, int col, boolean[][] visited, StringBuilder builder){
    visited[row][col] = true;
    builder.append(grid[row][col]);
    System.out.println(builder.toString());
    //the 2 loops are for the 8 movement directions
    for(int x = -1; x <= 1; x++){
        for(int y = -1; y <= 1; y++){
            //index bounds check
            if((row + x >= 0) && (row + x < rows) && (col + y >= 0) && (col + y < columns)){
                if(!visited[row + x][col + y]){
                    dfs(row + x, col + y, visited, builder);
                    // I tried changing it so that it passes a COPY of 'visited' and 'builder',
                    // but output still the same
                    dfs(row + x, col + y, Arrays.copyOf(visited, visited.length), new StringBuilder(builder));
                }

            }
        }
    }
}

我的代码输出不正确。这是它打印的内容：

这些数字是解决方案的一部分，但比那多得多。该错误可能与将同一对象传递到递归 dfs() 调用有关，但我尝试更改它以便它仅复制该对象，并且它仍然提供相同的输出。有什么想法吗？

Answer 1

您应该能够在不创建访问矩阵副本的情况下实现预期的输出。

重要的是在每次完成访问后将 visited[row][col] 设置为 false .

示例：

假设您已经遍历了“12”，现在还剩下“3”和“4”要访问。在当前状态下，visited 矩阵的“1”和“2”值设置为真，“3”和“4”设置为假。生成完所有以“12”开头的字符串后，您将开始查看所有以“13”开头的字符串。

但是看看这里发生了什么！您已将“2”的访问值设置为 true，因此以后不会生成包含“2”的字符串。

这就是为什么在从该点开始生成所有路径后必须将 visited[row][col] 设置为 false 的原因。

要真正理解这一点，请用笔和纸跟踪您的代码，您会更好地记住它。

注：

实际上，在上述示例中，您永远不会生成以 '13' 开头的字符串，因为 visited[1][1] 之前会被设置为 true，因此 3 将永远不会再次达到。我忽略了这个事实来说明一点。

为什么我建议不要对访问过的每个递归调用进行深拷贝？简单，节省时间和space。每次调用将花费 O(m*n) space 和时间来生成和存储新的访问矩阵。

这是正确代码的一种变体：

import java.util.*;

public class DFS{

    static char[][] grid;
    static int rows;
    static int columns;

    public static void main(String[] args) {
        //test grid. made it small so that solutions are easy to count
        grid = new char[][]{
                new char[]{'1', '2'},
                new char[]{'3','4'},
        };
        rows = grid.length;
        columns = grid[0].length;
        ArrayList<String>list = new ArrayList<>();
        dfs(0, 0, new boolean[rows][columns], new StringBuilder());
        //System.out.println(list);
    }

    public static void dfs(int row, int col, boolean[][] visited, StringBuilder builder){
        visited[row][col] = true;
        builder.append(grid[row][col]);
        System.out.println(builder);

        for(int x = -1; x <= 1; x++){
            for(int y = -1; y <= 1; y++){
                //index bounds check
                if((row + x >= 0) && (row + x < rows) && (col + y >= 0) && (col + y < columns)){
                    if(!visited[row + x][col + y]){
                        dfs(row + x, col + y, visited, builder);
                    }

                }
            }
        }
        visited[row][col]=false;
        builder.deleteCharAt(builder.length()-1);
    }
}

编辑：我忘记突出显示我删除当前 StringBuilder 的最后一个字符时添加的最后一行代码。这是回溯位，以便在生成所有“12xx”字符串后，删除“2”，将其替换为“3”，然后开始探索“13xx”字符串系列。

DFS 方法未产生预期输出

DFS method not producing expected output

java

algorithm

depth-first-search