时间戳

首页 > 解决方案 > DFS 方法没有产生预期的输出

java - DFS 方法没有产生预期的输出

问题描述

因此，目标是使用 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));
                }

            }
        }
    }
}

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

1
12
123
1234

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

标签： javaalgorithmdepth-first-search

解决方案

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

重要的是在每次 COMPLETE 访问后设置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。我忽略了这个事实来说明一点。

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

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

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”字符串系列。

推荐阅读