我有一个问题,我正在尝试练习,我无法弄清楚如何为其编写递归算法。我有一个布局如下的文件:
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;
}
}