4

我有一个问题，我正在尝试练习，我无法弄清楚如何为其编写递归算法。我有一个布局如下的文件：

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

这个问题来自 USACO。http://www.usaco.org/index.php?page=viewproblem2&cpid=189

问题陈述复制粘贴如下：

尽管 Bessie the cow 发现每一串平衡的括号在美学上都令人愉悦，但她特别喜欢她称之为“完美”平衡的字符串——由长度相同的 ('s 后跟 )'s 字符串组成。例如：

(((())))

一天穿过谷仓时，Bessie 发现地面上有一个 N x N 的马蹄铁网格，每个马蹄铁的方向看起来像 ( 或 )。从这个网格的左上角开始，Bessie 想四处走动捡起马蹄铁，这样她捡起的绳子就完美平衡了。 请帮助她计算她能得到的最长的完全平衡的弦的长度。

在每一步中，Bessie 都可以向上、向下、向左或向右移动。她只能移动到包含马蹄铁的网格位置，当她这样做时，她会拿起马蹄铁，这样她就不能再回到同一位置（因为它现在没有马蹄铁）。她首先拿起网格左上角的马蹄铁。Bessie 只捡起一系列形成完美平衡的弦的马蹄铁，因此她可能无法捡起网格中的所有马蹄铁。

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

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;
    }
}
4

1 回答 1

0

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

  • 开括号增加开括号的计数；
  • 如果你用星号关闭，你必须继续关闭并增加右括号；
  • 如果您正在关闭并且右括号的数量大于或等于打开的括号的数量，请停止并返回此值。

所有其余的代码都是语法糖。（从返回的访问项目列表中获得您想要的输出是微不足道的）。

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;
    }
}

}

于 2013-12-10T01:09:33.223 回答