java - 再帰的な方法を使用してすべてのパスを見つける

Question

練習しようとしている問題があり、そのための再帰アルゴリズムを作成する方法がわかりません。次のようにレイアウトされたファイルがあります。

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

この問題は USACO からのものです。http://www.usaco.org/index.php?page=viewproblem2&cpid=189

問題文を以下にコピペします。

牛の Bessie は、バランスの取れた括弧のすべてのストリングが美的に心地よいと感じていますが、彼女が「完全に」バランスが取れていると呼ぶストリングを特に楽しんでいます。例えば：

(((())))

ある日、納屋を歩いていると、Bessie は地面に N x N グリッドの蹄鉄を発見しました。そこでは、各蹄鉄が ( または ) のいずれかに見えるように配置されています。このグリッドの左上隅から始めて、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;
    }
}