Search all paths using recursive method

Question

I have a problem that I am trying to do in order to practice, and it’s hard for me to figure out how to write a recursive algorithm for it. I have a file that is laid out as follows:

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

This issue is taken from USACO. http://www.usaco.org/index.php?page=viewproblem2&cpid=189

The problem statement is copied below:

Despite the fact that Bessie the cow finds each line of balanced parentheses to be aesthetically pleasing, she especially likes the strings that she calls "perfectly" balanced - consisting of a line (followed by a line) that has the same length. For instance:

(((())))

While walking around the barn, Bessie once discovers a grid of N x N horseshoes on the ground, where each horseshoe is oriented so that it looks like (or). Starting from the upper left corner of this grid, Bessie wants to walk around the horseshoes so that the line she takes is perfectly balanced. Help her figure out the length of the longest perfectly balanced string she can get.

At every step, Bessie can move up, down, left, or right. She can only go to the place of the net containing the horseshoe, and when she does this, she lifts the horseshoe so that she can no longer go back to the same place (because now he lacks the horseshoe). It starts with picking up a horseshoe in the upper left corner of the grid. Bessie only picks up a series of horseshoes that form a perfectly balanced row, and therefore she will not be able to pick up all the horseshoes in the grid.

I'm having trouble trying to figure out how to create an algorithm that would find the best possible path recursively. Can someone point me in the right direction or any examples that I could take a look at to get an idea? I searched, but all the examples that I found were from one point to another, and did not find all possible paths in the matrix / array.

 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

The following algorithm will solve your problem. You can also use memoization to speed up work time. The idea is simple:

• when opening parentheses increases the number of open brackets;
• If you close a star, you must continue to close and increase closed parentheses;
• If you close, and the number of closed parentheses is greater than or equal to the number of open brackets, stop and return this value.

The rest of the code is syntactic sugar. (From the returned list of visited items, trivially complete the output you want).

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

}