时间戳

首页 > 解决方案 > 回溯问题，我不知道我的解决方案是否正确

java - 回溯问题，我不知道我的解决方案是否正确

问题描述

我正在练习回溯问题，这是问题描述： https ://practiceit.cs.washington.edu/problem/view/cs2/sections/recursivebacktracking/travel

编写一个 travel 方法，它接受整数 x 和 y 作为参数，并使用递归回溯通过重复使用三个移动之一来打印在二维平面中从 (0, 0) 到 (x, y) 的所有解决方案：

东（E）：右移 1（增加 x） 北（N）：上移 1（增加 y） 东北（NE）：上移 1 和右 1（增加 x 和 y）。

这是我得到的：我让它在一条路径上工作，但我不确定如何让它去探索所有其他可能的路径。我认为我的基本案例设计是错误的，但我不确定。我只想知道我应该首先解决什么，是基本情况还是我的整个概念是错误的。

public class PracticeRecordCode {
    public static void main(String[] args) {
        travel(1, 2);
    }
    public static String travel(int x, int y){
        List<String> allpath = new ArrayList<String>();

        String eachpath = "";

        return explore(0, 0, x, y, eachpath, allpath);
    }

    public static String explore(int x, int y, int des_x, int dest_y, String eachPath, List<String> allpath) {
        //Base case
        if(x == des_x && y== dest_y) {
                String result = "";
                if(isRepeated(eachPath, allpath)){
                    allpath.add(eachPath);
                    eachPath = "";
                }
            // Print all content from allpath
                for (String path : allpath) {
                    result += path + "\n";
                    System.out.println(path);
                }
                return result;
        } else {

            if(x == des_x && y != dest_y){
                eachPath += "N ";
                if(!allpath.contains(eachPath)) {
                    allpath.add(eachPath);
                }
                explore(x, y+1, des_x, dest_y, eachPath, allpath);
            } else if(x != des_x && y == dest_y) {
                eachPath += "E ";
                allpath.add(eachPath);
                explore(x + 1, y, des_x, dest_y, eachPath, allpath);
            } else {
                eachPath += "NE ";
                allpath.add(eachPath);
                explore(x + 1, y+1, des_x, dest_y, eachPath, allpath);
            }
        }
        return "";
    }

    // Check if this path has been done already
    public static boolean isRepeated(String path, List<String> allpath){
        return allpath.contains(path);
    }

}

标签： javarecursive-backtracking

解决方案

你可以试试我的代码。希望它可以为您提供解决方案->

public static void main(String[] args) {
    baktracking(new boolean[5][3], 0, 0, 2, 2, "");
}

static void baktracking(boolean m[][], int x, int y, int dx, int dy, String ans) {
    if (x == dx && y == dy) {
        System.out.println(ans);
        return;
    }
    if (x < 0 || y < 0 || x >= m.length || y >= m[0].length) {
        return;
    }
    m[x][y] = true;
    baktracking(m, x, y +1, dx, dy, ans + "E" + " ");
    baktracking(m, x + 1, y, dx, dy, ans + "N" + " ");
    baktracking(m, x + 1, y + 1, dx, dy, ans + "NE" + " ");
    m[x][y] = false;
}

推荐阅读