Небольшие изменения в заданном алгоритме

Question

Речь идет об изменении алгоритма лабиринта.

Что я имею в виду? Мы получили двумерный массив, заполненный 0 и 1, где 0 означает «невозможно пройти» и 1 для «возможно пройти». Этот алгоритм находит свой путь от x до y (также известный пример: cat to mouse). И это именно то, что делает следующий алгоритм.

В качестве вклада мы получили:

{1, 0, 0,}, 
{1, 1, 0}, 
{0, 1, 1} }; 

И вывод:

(0,0) // ressembles the coordinates of the 1 in top left corner 
(1,0) // ressembles the 1 under the first 1 I just explained 
(1,1) // ... 
(2,1) 
(2,2) 

Я хочу изменить некоторые мелочи:

1. Изменить начальную и конечную позицию (этот алгоритм начинает в левом верхнем углу и заканчивается в правом нижнем углу) - Я хочу, чтобы мой начал в левом нижнем углу и заканчивал верхний правый.
2. Этот алгоритм может двигаться только вниз и вправо - я хочу только двигаться вверх и вправо.

Какие изменения должны быть сделаны, я уверен, но я не знаю, как код, который: Для 1.) проблема кажется:

public List<Coordinate> solve() { 
     return getMazePath(0, 0, new Stack<Coordinate>()); 
    } 

Каким-то образом, я нужно сделать 0-1 со вторым нолем, но как, если у меня нет доступа к объявлениям x и y? Я действительно верю, что 0-1 заставит меня начать снизу слева, а не вверху слева, верно?

Для 2.) изменяется для столбца, также известно, что y необходимо выполнить. Вместо +1 требуется -1, это правильно?

Извините за эту стену текста, я действительно пытался держать его коротким, но мне кажется, не удалось: P Во всяком случае, я надеюсь, что кто-то будет читать это ^^

алгоритм без изменений:

import java.util.Arrays; 
import java.util.*; 

final class Coordinate { 
    private final int x; 
    private final int y; 

    public Coordinate(int x, int y) { 
     this.x = x; 
     this.y = y; 
    } 

    public int getX() { 
     return x; 
    } 

    public int getY() { 
     return y; 
    } 
} 

public class Alg { 

    private final int[][] maze; 

    public Alg(int[][] maze) { 
     if (maze == null) { 
      throw new NullPointerException("The input maze cannot be null"); 
     } 
     if (maze.length == 0) { 
      throw new IllegalArgumentException("The size of maze should be greater than 0"); 
     } 

     this.maze = maze; 
    } 

    public List<Coordinate> solve() { 
     return getMazePath(0, 0, new Stack<Coordinate>()); 
    } 

    private List<Coordinate> getMazePath(int row, int col, Stack<Coordinate> stack) { 
     assert stack != null; 

     stack.add(new Coordinate(row, col)); 

     if ((row == maze.length - 1) && (col == maze[0].length - 1)) { 
      Coordinate[] coordinateArray = stack.toArray(new Coordinate[stack.size()]); 
      return Arrays.asList(coordinateArray); 
     } 

     for (int j = col; j < maze[row].length; j++) { 

      if ((j + 1) < maze[row].length && maze[row][j + 1] == 1) { 
       return getMazePath(row, j + 1, stack); 
      } 

      if ((row + 1) < maze.length && maze[row + 1][col] == 1) { 
       return getMazePath(row + 1, col, stack); 
      } 
     } 

     return Collections.emptyList(); 
    } 


    public static void main(String[] args) { 
     int[][] m = { {1, 0, 0,}, 
         {1, 1, 0}, 
         {0, 1, 1} }; 

     Alg maze = new Alg(m); 

     for (Coordinate coord : maze.solve()) { 
      System.out.println("("+coord.getX() + "," + coord.getY()+")"); 
     } 
    } 
} 

Answer 1

Посмотрите на объявление метода для getMazePath. Ток 0, 0 передается в качестве аргументов row и col. Поэтому вместо отправки 0, 0 этому методу, который в настоящее время кодируется, вы отправите 2, 0 (для строки 2, столбец 0, внизу слева).

Направленные движения в for петли внутри этого getMazePath() метода, два, если утверждения проверить, есть ли 1 в колонке j + 1 (колонка справа) или в строке row + 1 (строки ниже текущей). Вы должны изменить их, чтобы использовать минус вместо плюса для перемещения влево или вверх, соответственно.