使用递归方法查找所有路径

Question

我在练习时遇到了一个问题，我很难想出如何为它编写递归算法。我有一个像这样排列的文件：

4
(())
()((
(()(
))))

这个问题是由美援部队提出的。http://www.usaco.org/index.php?page=viewproblem2&cpid=189

问题说明复制粘贴如下：

尽管贝西觉得每一串平衡的圆括号在美观上都是令人愉悦的，但她特别喜欢她称之为“完美”平衡的字符串--由一串(后面跟着一串)的字符串组成，长度相同。例如： () 有一天，贝西在谷仓里走来走去，发现地上有一个N个马蹄形网格，每个马蹄铁都是定向的，看起来像是(或)。从这个网格的左上角开始，贝茜想四处走动，捡起马蹄铁，这样她捡起的绳子就能完全平衡。请帮她计算她能得到的最长的完全平衡的字符串的长度。 在每一步中，贝茜都可以向上、向下、左或右移动。她只能移动到包含马蹄铁的网格位置，当她这样做时，她会捡起马蹄铁，这样她就不能再搬回原来的位置了(因为它现在没有马蹄铁了)。她首先拿起栅格左上角的马蹄铁。贝茜只拿起一系列马蹄铁，这些马蹄铁形成了一个完美平衡的弦，因此她可能无法在网格中捡起所有的马蹄铁。

我遇到了一些问题，试图弄清楚如何创建一个递归找到最佳路径的算法。谁能给我指出正确的方向，或者有什么我可以看的例子来得到一个想法？我一直在搜索，但我找到的所有示例都是从一个点到另一个点，而不是在一个矩阵/数组中找到所有可能的路径。

package bessiehorseshoe;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class BessieHorseShoe {

    int answer = 0;
    int matrixSize = 0;

    public static void main(String[] args) throws IOException {
        BessieHorseShoe goBessieGo = new BessieHorseShoe();
    }

    BessieHorseShoe() throws IOException {
        int rowFilled = 0;
        int currentColumn = 0;
        int character = 0;

        BufferedReader inputFile = new BufferedReader(new FileReader("hshoe.in"));
        String inputLine = inputFile.readLine();
        matrixSize = Character.digit(inputLine.charAt(0), 10);
        System.out.println(matrixSize);

        char[][] pMatrix = new char[matrixSize][matrixSize];

        while ((character = inputFile.read()) != -1) {
            char c = (char) character;
            if (c == '(' || c == ')') {
                pMatrix[rowFilled][currentColumn] = c;
                System.out.print(pMatrix[rowFilled][currentColumn]);
                rowFilled++;
                if (rowFilled == matrixSize) {
                    currentColumn++;
                    rowFilled = 0;
                    System.out.println();
                }
            }
        }
        matchHorseShoes(pMatrix);
    }

    public int matchHorseShoes(char[][] pMatrix) {
        if (pMatrix[0][0] == ')') {
            System.out.println("Pattern starts with ')'. No possible path!");
            return 0;
        }
        System.out.println("Works");
        return 0;
    }
}

Answer 1

下面的算法将解决您的问题。您也可以使用回忆录来加快运行时间。这个想法很简单：

• 当开括号时，打开括号的计数增加；
• 如果您的明星关闭，您必须继续关闭和增加关闭括号；
• 如果您正在结束，且关闭括号的数目大于或等于打开的括号数，则停止并返回此值。

其余的代码都是语法糖。(从所访问的项目返回的列表中可以获得您想要的输出)。

import java.util.LinkedList;
import java.util.List;

public class USACO {

static class Path {

    public List<String> items;
    public int value;

    public Path() {
        this.items = new LinkedList<String>();
        this.value = 0;
    }

}

public static void main(final String[] args) {
    final int n = 5;
    final String[][] input = new String[n][n];
    // Create a random input of size n
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < n; x++) {
            input[y][x] = Math.random() < 0.5 ? "(" : ")";
            System.out.print(input[y][x] + " ");
        }
        System.out.println();
    }
    final Path bestPath = longestPath(n, input, 0, 0, 0, 0, input[0][0] == "(");
    System.out.println("Max:" + bestPath.value + "\n" + bestPath.items);
}

public static Path longestPath(final int n, final String[][] input, final int x, final int y, int numberOpened, int numberClosed,
        final boolean wasOpening) {
    if (input == null) {
        return new Path();
    } else if (!wasOpening && (numberClosed >= numberOpened)) { // Reached a solution
        final Path path = new Path();
        path.value = numberOpened;
        path.items.add("(" + x + "," + y + ")");
        return path;
    } else if ((x < 0) || (y < 0) || (x >= n) || (y >= n)) { // Out of bound
        return new Path();
    } else if (input[y][x] == "") { // Already visited this item
        return new Path();
    } else {
        final String parenthese = input[y][x];
        // Increment the number of consecutive opened or closed visited
        if (parenthese.equals("(")) {
            numberOpened++;
        } else {
            numberClosed++;
        }
        input[y][x] = ""; // Mark as visited
        Path bestPath = new Path();
        bestPath.value = Integer.MIN_VALUE;
        // Explore the other items
        for (int dy = -1; dy <= 1; dy++) {
            for (int dx = -1; dx <= 1; dx++) {
                if (((dy == 0) || (dx == 0)) && (dy != dx)) { // go only up, down, left, right
                    final boolean opening = (parenthese == "(");
                    if (wasOpening || !opening) {
                        // Find the longest among all the near items
                        final Path possiblePath = longestPath(n, input, x + dx, y + dy, numberOpened, numberClosed, opening);
                        if (possiblePath.value > bestPath.value) {
                            bestPath = possiblePath;
                            bestPath.items.add("(" + x + "," + y + ")");
                        }
                    }
                }
            }
        }
        input[y][x] = parenthese; // mark as not visited
        return bestPath;
    }
}

}