все возможные пути для робота

Question

Представьте себе робота, сидящего в верхнем левом углу сетки NxN. Робот может двигаться только в двух направлениях: вправо и вниз. Представьте, что определенные квадраты являются «пределами», так что робот не может на них наступить. Разработать алгоритм для получения всех возможных путей для робота.

Вот ссылка, которую я получил, я думаю, что реализация неверна, поскольку она находит только один путь, отличный от всех возможных путей (более подробно, в строке 10, робот только спускается, если нет правильного пути вправо. Но чтобы найти все возможные пути, робот должен попробовать как вправо, так и вниз)? Хочу подтвердить, что мое понимание верное.

ArrayList<Point> current_path = new ArrayList<Point>(); 
public static boolean getPaths(int x, int y) { 
     Point p = new Point(x, y); 
     current_path.add(p); 
     if (0 == x && 0 == y) return true; // current_path 
     boolean success = false; 
     if (x >= 1 && is_free(x - 1, y)) { // Try right 
     success = getPaths(x - 1, y); // Free! Go right 
     } 
     if (!success && y >= 1 && is_free(x, y - 1)) { // Try down 
     success = getPaths(x, y - 1); // Free! Go down 
     } 
     if (!success) { 
     current_path.remove(p); // Wrong way! 
     } 
     return success; 
} 

спасибо заранее, Лин

Answer 1

Вот что вы можете сделать:

public static class Point { 
    int x, y; 
    public Point (int x, int y) { 
     this.x = x; 
     this.y = y; 
    } 

    @Override 
    public String toString() { 
     return String.format("[%d, %d]", x, y); 
    } 
} 

public static void getPathsRec(int x, int y, Deque<Point> currentPath, 
           List<List<Point>> paths) { 
    if (x == 0 && y == 0) { 
     List<Point> path = new ArrayList<Point>(); 
     for (Point p : currentPath) 
      path.add(p); 
     paths.add(path); 
     //System.out.println(currentPath); 
     return; 
    } 

    if (x > 0 && is_free(x-1, y)) { 
     currentPath.push(new Point(x-1, y)); 
     getPathsRec(x-1, y, currentPath, paths); 
     currentPath.pop(); 
    } 

    if (y > 0 && is_free(x, y-1)) { 
     currentPath.push(new Point(x, y-1)); 
     getPathsRec(x, y-1, currentPath, paths); 
     currentPath.pop(); 
    } 
} 

static int n = 2; 
public static List<List<Point>> getPaths() { 
    List<List<Point>> paths = new ArrayList<List<Point>>(); 
    Deque<Point> d = new ArrayDeque<Point>(); 
    d.push(new Point(n-1, n-1)); 
    getPathsRec(n - 1, n - 1, d, paths); 
    //System.out.println(paths); 
    return paths; 
} 

Это простой backtracking. Идея состоит в том, чтобы вернуться к следующему состоянию рекурсивно, но чтобы убедиться, что после вызова состояние возвращается к предыдущему состоянию (например, до вызова). Здесь это делается с выталкиванием элемента из Deque.

Обратите внимание, что для простоты можно ввести новый класс Path, который будет что-то вроде:

class Path { 
    List<Point> points; 
} 

, чтобы сделать код более читаемым. Тогда getPaths() вернет List<Path>, что намного приятнее.

Также рассмотреть переопределение getPathsRec иметь подпись getPathsRec(Point p, Deque<Point>, List<Path>), который имеет один аргумент Point вместо того x, y. Наличие x, y кажется излишним, учитывая тот факт, что вы определили class Point. Снова это заставило бы его выглядеть лучше.

Answer 2

Ваше решение неверно, так как оно достигает (0 == x && y==0), значение success всегда будет установлено в true. Следовательно, он не войдет позже. if

Ниже приведен образец ответа на вашу проблему. Он использует алгоритм обратного отслеживания:

public class test { 
    static int n = 3; //substitute your n value here 
    static ArrayList<Point> current_path = new ArrayList<Point>(); 
    static boolean[][] blockedCell = new boolean[n][n]; 
    public static void FindAllWay(int x, int y) 
    { 
     if (x <0 || y < 0) return; 
     Point p = new Point(x, y); 
     current_path.add(p); 

     if (0 == x && 0 == y){ 
      System.out.println(current_path.toString()); 
      current_path.remove(current_path.size()-1); 
      return; 
     } 

     if ((x > 0) && !blockedCell[x-1][y]) //go right 
     { 
      blockedCell[x-1][y] = true; 
      FindAllWay(x-1, y); 
      blockedCell[x-1][y] = false; 
     } 
     if ((y > 0) &&!blockedCell[x][y-1]) // go down 
     { 
      blockedCell[x][y-1] = true; 
      FindAllWay(x, y-1); 
      blockedCell[x][y-1] = false; 
     } 
     current_path.remove(current_path.size()-1); 

    } 

    public static void main(String[] args) 
    { 
     FindAllWay(n-1,n-1); 
    } 
}