Алгоритм поиска всех путей в сетке NxN

Я не вижу никаких указаний на препятствия в вашем вопросе, поэтому я предполагаю, что их нет.

Обратите внимание, что роботы должны принимать ровно 2n шагов, чтобы добраться до правого угла. Таким образом, он не может сделать больше, чем 2n ходов.

Начнем с этого частного случая: [найти все пути в правом нижнем углу]

Робот может точно choose(n,2n) = (2n)!/(n!*n!) : Ему нужно только выбрать, какой из этих 2n движений будет правильным, остальные – вниз [и есть ровно n из тех]
Чтобы создать возможные пути: просто сгенерируйте все двоичные векторы размером 2n с точностью до n 1. Знаки 1 будут показывать правильные ходы, а 0 будут показывать вниз.

Теперь давайте разберем его на все пути:
Сначала вам нужно выбрать длину пути. Просто перебирайте все возможности: 0 <= i <= 2n , где i - длина пути. в этом пути есть max(0,in) <= j <= min(i,n) правые шаги.
Чтобы создать все возможности, следуйте этому псевдокоду:

 for each i in [0,2n]: for each j in [max(0,in),min(i,n)]: print all binary vectors of size i with exactly j bits set to 1 

Примечание1: печать всех двоичных векторов размера i с j битами, установленными в 1, может быть вычислительной экспансивной. Это ожидается, так как существует экспоненциальное число решений для робота.
Примечание2: Для случая i=2n вы получите j in [n,n] , как мы ожидали увидеть [частный случай, описанный выше].

 public static int computePaths(int n){ return recursive(n, 1, 1); } public static int recursive(int n, int i, int j){ if( i == n || j == n){ //reach either border, only one path return 1; } return recursive(n, i + 1, j) + recursive(n, i, j + 1); } 

Чтобы найти все возможные пути:
все еще используя рекурсивный метод. Переменная пути назначается «» в начале, а затем добавляет каждую точку, посещенную в «путь». Возможный путь формируется при достижении точки (n, n), а затем добавляется в список.

Каждый путь обозначается как строка, например «(1,1) (2,1) (3,1) (4,1) (4,2) (4,3) (4,4)». Все возможные пути хранятся в списке строк.

 public static List robotPaths(int n){ List pathList = new ArrayList(); getPaths(n, 1,1, "", pathList); return pathList; } public static void getPaths(int n, int i, int j, String path, List pathList){ path += String.format(" (%d,%d)", i , j); if( i ==n && j == n){ //reach the (n,n) point pathList.add(path); }else if( i > n || j > n){//wrong way return; }else { getPaths(n, i +1, j , path, pathList); getPaths(n, i , j +1, path, pathList); } } 

https://math.stackexchange.com/questions/104032/finding-points-in-a-grid-with-exactly-k-paths-to-them – посмотрите здесь, на мое решение. Кажется, что это именно то, что вам нужно (да, заявления несколько разные, но в общем случае они одинаковы).

Это значит, что робот может идти 4 направления, а не только 2, но рекурсивное решение ниже (в Javascript) работает, и я попытался сделать его максимально понятным:

 //first make a function to create the board as an array of arrays var makeBoard = function(n) { var board = []; for (var i = 0; i < n; i++) { board.push([]); for (var j = 0; j < n; j++) { board[i].push(false); } } board.togglePiece = function(i, j) { this[i][j] = !this[i][j]; } board.hasBeenVisited = function(i, j) { return !!this[i][j]; } board.exists = function(i, j) { return i < n && i > -1 && j < n && j > -1; } board.viablePosition = function(i, j) { return board.exists(i, j) && !board.hasBeenVisited(i,j); } return board; }; var robotPaths = function(n) { var numPaths = 0; //call our recursive function (defined below) with a blank board of nxn, with the starting position as (0, 0) traversePaths(makeBoard(n), 0, 0); //define the recursive function we'll use function traversePaths(board, i, j) { //BASE CASE: if reached (n - 1, n - 1), count as solution and stop doing work if (i === (n - 1) && j === (n - 1)) { numPaths++; return; } //mark the current position as having been visited. Doing this after the check for BASE CASE because you don't want to turn the target position (ie when you've found a solution) to true or else future paths will see it as an unviable position board.togglePiece(i, j); //RECURSIVE CASE: if next point is a viable position, go there and make the same decision //go right if possible if (board.viablePosition(i, j + 1)) { traversePaths(board, i, j + 1); } //go left if possible if (board.viablePosition(i, j - 1)) { traversePaths(board, i, j - 1); } //go down if possible if (board.viablePosition(i + 1, j)) { traversePaths(board, i + 1, j); } //go up if possible if (board.viablePosition(i - 1, j)) { traversePaths(board, i - 1, j); } //reset the board back to the way you found it after you've gone forward so that other paths can see it as a viable position for their routes board.togglePiece(i, j); } return numPaths; }; 

Чистая версия:

 var robotPaths = function(n, board, i, j) { board = board || makeBoard(n), i = i || 0, j = j || 0; // If current cell has been visited on this path or doesn't exist, can't go there, so do nothing (no need to return since there are no more recursive calls below this) if (!board.viablePosition(i, j)) return 0; // If reached the end, add to numPaths and stop recursing if (i === (n - 1) && j === (n - 1)) return 1; // Mark current cell as having been visited for this path board.togglePiece(i, j); // Check each of the four possible directions var numPaths = robotPaths(n, board, i + 1, j) + robotPaths(n, board, i - 1, j) + robotPaths(n, board, i, j + 1) + robotPaths(n, board, i, j - 1); // Reset current cell so other paths can go there (since board is a pointer to an array that every path is accessing) board.togglePiece(i, j); return numPaths; } 

Так:

 robotPaths(5); //returns 8512 

Сценарий:
1. Представьте, что NxN нулевая индексированная matrix.
2. Исходное положение робота – верхний левый угол, т. Е. (N-1, N-1)
3. Робот хочет достичь нижнего правого угла, т. Е. На (0,0)

Решение:
– В любом возможном решении робот переместит N шагов прав и N шагов вниз, чтобы достичь (0,0), или мы можем сказать, что у начального робота есть разрешение на перемещение N шагов прав и N шагов вниз.
– Когда робот движется вправо, мы уменьшаем оставшееся количество правильных шагов на 1, то же самое для движения вниз.
– В каждой позиции (за исключением границы, где у нее будет только один вариант), у робота есть два варианта: один – это может пойти вниз или другой, это может пойти правильно.
– Это прекратится, когда робот не будет иметь никаких оставшихся шагов.

** Ниже кода также есть метод драйвера main (), вы можете изменить значение N. N может быть> = 1

 public class RobotPaths { public static int robotPaths(int down, int right, String path) { path = path+ down +","+ right +" "; if(down==0 && right==0) { System.out.println(path); return 1; } int counter = 0; if(down==0) counter = robotPaths(down, right-1, path); else if(right==0) counter = robotPaths(down-1, right, path); else counter = robotPaths(down, right-1, path) + robotPaths(down-1, right, path); return counter; } public static void main(String[] args) { int N = 1; System.out.println("Total possible paths: "+RobotPaths.robotPaths(N-1, N-1, "")); } 

}

Вот c # версия (только для справки), чтобы найти уникальные пути (обратите внимание, что это версия, которая возвращает количество путей с использованием динамического программирования (запоминание – ленивое) – вычисление количества ходов от верхнего левого угла до нижнего правого с движением в любом направлении ) (вы можете обратиться к моему блогу для получения дополнительной информации: http://codingworkout.blogspot.com/2014/08/robot-in-grid-unique-paths.html )

 Tuple[][] GetUniquePaths(int N) { var r = this.GetUniquePaths(1, 1, N); return r; } private Tuple[][] GetUniquePaths(int row, int column, int N) { if ((row == N) && (column == N)) { var r = new Tuple[1][]; r[0] = new Tuple[] { new Tuple(row, column) }; return r; } if ((row > N) || (column > N)) { return new Tuple[0][]; } var uniquePathsByMovingDown = this.GetUniquePaths(row + 1, column, N); var uniquePathsByMovingRight = this.GetUniquePaths(row, column + 1, N); List[]> paths = this.MergePaths(uniquePathsByMovingDown, row, column).ToList(); paths.AddRange(this.MergePaths(uniquePathsByMovingRight, row, column)); return paths.ToArray(); } 

где

 private Tuple[][] MergePaths(Tuple[][] paths, int row, int column) { Tuple[][] mergedPaths = new Tuple[paths.Length][]; if (paths.Length > 0) { Assert.IsTrue(paths.All(p => p.Length > 0)); for (int i = 0; i < paths.Length; i++) { List> mergedPath = new List>(); mergedPath.Add(new Tuple(row, column)); mergedPath.AddRange(paths[i]); mergedPaths[i] = mergedPath.ToArray(); } } return mergedPaths; } 

Тесты модhive

 [TestCategory(Constants.DynamicProgramming)] public void RobotInGridTests() { int p = this.GetNumberOfUniquePaths(3); Assert.AreEqual(p, 6); int p1 = this.GetUniquePaths_DP_Memoization_Lazy(3); Assert.AreEqual(p, p1); var p2 = this.GetUniquePaths(3); Assert.AreEqual(p1, p2.Length); foreach (var path in p2) { Debug.WriteLine("==================================================================="); foreach (Tuple t in path) { Debug.Write(string.Format("({0}, {1}), ", t.Item1, t.Item2)); } } p = this.GetNumberOfUniquePaths(4); Assert.AreEqual(p, 20); p1 = this.GetUniquePaths_DP_Memoization_Lazy(4); Assert.AreEqual(p, p1); p2 = this.GetUniquePaths(4); Assert.AreEqual(p1, p2.Length); foreach (var path in p2) { Debug.WriteLine("==================================================================="); foreach (Tuple t in path) { Debug.Write(string.Format("({0}, {1}), ", t.Item1, t.Item2)); } } } 

Вот полная реализация, которая работает как для прямоугольной, так и для квадратной сетки. Я оставлю вас, чтобы выяснить, как позаботиться о избытке «=>» в конце каждого пути.

  import java.util.Arraylist; public class PrintPath { static ArrayList paths = new ArrayList(); public static long getUnique(int m, int n, int i, int j, String pathlist) { pathlist += ("(" + i + ", " + (j) + ") => "); if(m == i && n == j) { paths.add(pathlist); } if( i > m || j > n) { return 0; } return getUnique(m, n, i+1, j, pathlist)+getUnique(m, n, i, j+1, pathlist); } public static void printPaths() { int count = 1; System.out.println("There are "+paths.size() + " unique paths: \n"); for (int i = paths.size()-1; i>=0; i--) { System.out.println( "path " + count + ": " + paths.get(i)); count++; } } public static void main(String args[]) { final int start_Point = 1; int grid_Height = 2; int grid_Width = 2; getUnique(grid_Height, grid_Width, start_Point, start_Point, ""); printPaths(); } } 

Если вам просто нужно подсчитать допустимые пути:

Предположим, у вас есть matrix n * m matrix, и вы установите все ячейки равными нулю, а ячейки «offlimit» – -1.

Затем вы можете решить проблему с динамическим программированием:

 // a is a matrix with 0s and -1s // n, m are the dimensions // M is 10^9-7 incase you have a large matrix if (a[0][0] == 0) a[0][0] = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (a[i][j] == -1) continue; if (i > 0) a[i][j] = (a[i][j] + max(a[i-1][j], 0LL)) % M; if (j > 0) a[i][j] = (a[i][j] + max(a[i][j-1], 0LL)) % M; } } // answer at lower right corner cout << a[n-1][m-1]; 

Быстрое сверкание без рекурсии или раздутых структур данных.

ПРИМЕЧАНИЕ: это было удалено из-за дублирования, но поскольку это лучший stream в этой теме, я удалил свой ответ из другого места и добавлю это здесь.

Ниже приведен код Java для подсчета всех возможных путей из верхнего левого угла в нижний правый угол матрицы NXN.

 public class paths_in_matrix { /** * @param args */ static int n=5; private boolean[][] board=new boolean[n][n]; int numPaths=0; paths_in_matrix(){ for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { board[i][j]=false; } } } private void togglePiece(int i,int j){ this.board[i][j]=!this.board[i][j]; } private boolean hasBeenVisited(int i,int j){ return this.board[i][j]; } private boolean exists(int i,int j){ return i < n && i > -1 && j < n && j > -1; } private boolean viablePosition(int i,int j){ return exists(i, j) && !hasBeenVisited(i,j); } private void traversePaths(int i,int j){ //BASE CASE: if reached (n - 1, n - 1), count as path and stop. if (i == (n - 1) && j == (n - 1)) { this.numPaths++; return; } this.togglePiece(i, j); //RECURSIVE CASE: if next point is a viable position, go there and make the same decision //go right if possible if (this.viablePosition(i, j + 1)) { traversePaths(i, j + 1); } //go left if possible if (this.viablePosition(i, j - 1)) { traversePaths( i, j - 1); } //go down if possible if (this.viablePosition(i + 1, j)) { traversePaths( i + 1, j); } //go up if possible if (this.viablePosition(i - 1, j)) { traversePaths(i - 1, j); } //reset the board back to the way you found it after you've gone forward so that other paths can see it as a viable position for their routes this.togglePiece(i, j); } private int robotPaths(){ traversePaths(0,0); return this.numPaths; } public static void main(String[] args) { paths_in_matrix mat=new paths_in_matrix(); System.out.println(mat.robotPaths()); } } 

 int N; function num_paths(intx,int y) { int[][] arr = new int[N][N]; arr[N-1][N-1] = 0; for(int i =0;i=0;i--) { for(int j=N-2;j>=0;j--) { arr[i][j]= arr[i+1][j]+arr[i][j+1]; } } return arr[0][0]; }