Java лабиринт внутри стен и получить все возможные пути

Question

Я знаю, что здесь много других решателей лабиринтов.Хотя я хотел бы иметь свой собственный подход и думаю, что моя проблема немного отличается от других.

На данный момент, вот что я начал, и, надеюсь, я смогу достичь того, что имею в виду намомент.

    private static int getPossiblePaths(File f) throws IOException {

    int counts = 0; // hope to return all possible paths

    // read input file then put it on list string
    List<String> lines = Files.lines(f.toPath()).collect(Collectors.toList());

    // get the row and column (dimensions)
    String[] dimensions = lines.get(0).split(",");

    //initalize sub matrix of the maze dimensions and ignoring the top and bottom walls
    int[][] mat = new int[Integer.valueOf(dimensions[0]) - 2 ][Integer.valueOf(dimensions[1]) - 2];    

    //for each line in the maze excluding the boundaries (top and bottom)
    for( int i = 2 ; i < lines.size() - 1  ; i++) {
        String currLine = lines.get(i);
        int j = 0; 
        for(char c : currLine.toCharArray()) {
            mat[i-2][j] = (c=='*' ? 'w' : c=='A' ? 'a' : c=='B' ? 'b' : 's');

            // some conditional statements here

        }  
    }
// or maybe some conditional statements here outside of the loop

    return counts;

}

И лабиринт из текстового файла выглядит следующим образом.Обратите внимание, что A может быть где угодно и таким же, как B. Допустимы только движения: вправо и вниз .

5,5
*****
*A  *
*   *
*  B*
*****

Ожидаемый выход для лабиринта вышеравно 6 (возможные пути от A до B).

РЕДАКТИРОВАТЬ: Также лабиринт из текстового файла может быть таким:

8,5
********
* A    *
*     B*
*      *
********

Так что с моим текущим кодом, он получаетразмеры (первая строка) и удаление верхней и нижней части лабиринта (границы).Таким образом, в массиве mat хранится только 3 строки символов.И некоторая кодировка каждого символа текстового файла (# = w (стена), A = a (начало), B = b (конец), иначе s (пробел))

Я хотел бы иметь некоторыеусловные операторы внутри foreach для хранения каждого из символов внутри ArrayList.Хотя я не уверен, что этот подход только усложнит мою жизнь.

Любые предложения, советы, советы или другие более простые подходы от вас, ребята, будут высоко оценены!Спасибо

Answer 1

Идея создать mat прекрасна.Я бы не стал снимать первую и последнюю строку, так как на самом деле с ними будет легче работать, если вы их сохраните.Таким образом, ссылка на строку, такая как i-1, не будет выходить за пределы диапазона, когда вы находитесь за пределами стены.

Я бы также не хранил там символы, такие как w, но конкретные цифры, например -1 за стену, 0 бесплатно.Также сохраните 0 для «A» и «B».При встрече с этими двумя буквами вы можете сохранить их координаты в определенных переменных (например, rowA, colA, rowB, colB).Возможно, вам придется проверить, находится ли B внизу справа от A, так как в противном случае B определенно не будет доступен из A.

Поэтому я бы определил mat следующим образом (обратите внимание, что я изменил размеры, потому что ваш второйВ примере показано, что в первой строке входных данных они расположены в указанном порядке):

    int[][] mat = new int[Integer.valueOf(dimensions[1])]
                         [Integer.valueOf(dimensions[0])];

    int colA = mat[0].length;
    int rowA = 0;
    int colB = colA;
    int rowB = 0;
    for (int i = 0; i < mat.length; i++) {
        String currLine = lines.get(i+1);
        int j = 0;
        for (char c : currLine.toCharArray()) {
            mat[i][j] = c == '*' ? -1 : 0;
            if (c == 'B') {
                if (colA > j) return 0; // B unreachable from A
                rowB = i;
                colB = j;
            } else if (c == 'A') {
                if (colB < j) return 0; // B unreachable from A
                rowA = i;
                colA = j;
            }
            j++;
        }
    }

При этой настройке вы можете повторно использовать mat, чтобы сохранить количество путей от A до текущей позиции.Значение 0 в A должно быть установлено в 1 (есть один путь от A до A), а затем необходимо сложить значение из ячейки сверху и слева, убедившись, что -1 рассматривается как0.

    mat[rowA][colA] = 1;
    for (int i = rowA; i <= rowB; i++) {
        for (int j = colA; j <= colB; j++) {
            if (mat[i][j] == 0) { // not a wall?
                // count the number of paths that come from above,
                //   plus the number of paths that come from the left
                mat[i][j] = Math.max(0, mat[i-1][j]) + Math.max(0, mat[i][j-1]);
            }
        }
    }
    return mat[rowB][colB]; // now this has the number of paths we are looking for

Хотя рекурсивный метод также будет работать, я бы предложил описанный выше подход динамическое программирование , поскольку таким образом вы избегаете повторного подсчета для определенной ячейки несколько раз (когдаприходя туда через разные пути DFS).Это решение имеет линейную сложность по времени.

Answer 2

Я предлагаю простую рекурсию с двумя вызовами: вниз и вправо.

Это код:

import java.io.File;
import java.io.IOException;
import java.lang.invoke.MethodHandles;
import java.net.URISyntaxException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.List;
import java.util.stream.Collectors;

public class JavaMazeInsideOfWallsAndGetAllPossiblePaths {

    public static void main(String[] args) throws IOException, URISyntaxException {
        Path mazePath = Paths.get( MethodHandles.lookup().lookupClass().getClassLoader()
                  .getResource("maze.txt").toURI());
        File mazeFile = mazePath.toFile();
        System.out.println(getPossiblePaths(mazeFile));

    }

    private static int getPossiblePaths(File f) throws IOException {
        // read input file then put it on list string
        List<String> lines = Files.lines(f.toPath()).collect(Collectors.toList());

        // get the row and column (dimensions)
        String[] dimensions = lines.get(0).split(",");

        //initalize sub matrix of the maze dimensions and ignoring the top and bottom walls
        int[][] mat = new int[Integer.valueOf(dimensions[0]) - 2 ][Integer.valueOf(dimensions[1]) - 2];

        int fromRow = -1, fromCol = -1, toRow = -1, toCol = -1;

        for( int i = 2 ; i < lines.size() - 1  ; i++) {
            String currLine = lines.get(i);
            int j = 0;
            for(char c : currLine.toCharArray()) {
                switch(c) {
                case '*':
                    continue; // for loop
                case 'A':
                    mat[i-2][j] = 0;
                    fromRow = i-2;
                    fromCol = j;
                    break;
                case 'B':
                    mat[i-2][j] = 2;
                    toRow = i-2;
                    toCol = j;
                    break;
                default:
                    mat[i-2][j] = 1;
                }
                j++;
            }
        }

        return getPossiblePathsRecursive(mat, fromRow, fromCol, toRow, toCol);
    }

    private static int getPossiblePathsRecursive(int[][] mat, int i, int j, int rows, int columns) throws IOException {

        if(i > rows || j > columns) {
            return 0;
        }

        if(mat[i][j] == 2) {
            return 1;
        }

        return getPossiblePathsRecursive(mat, i+1, j, rows, columns) +
               getPossiblePathsRecursive(mat, i, j + 1, rows, columns);
    }
}

Примечания: 1. Этап проверки пропускается (при условии, что вводданные в правильном формате) 2. Стены игнорируются (при условии, что всегда есть 4 стены - первая строка, последняя строка, первый столбец, последний столбец. Предполагается, что эти стены представлены как '*')