Представьте себе робота, сидящего в верхнем левом углу сетки NxN. Робот может двигаться только в двух направлениях: вправо и вниз. Сколько возможных путей для робота?
Я мог бы найти решение этой проблемы в Google, но я не очень понимаю объяснения. Я пытаюсь четко понять логику о том, как ее решить и реализовать на Java. Любая помощь приветствуется.
Обновление: это вопрос интервью. Пока я пытаюсь добраться до нижнего правого конца и печатать возможные пути.
Я не вижу никаких признаков препятствий в вашем вопросе, поэтому мы можем предположить, что их нет.
Обратите внимание, что для сетки n + 1 на n + 1, робот должен сделать ровно 2n шагов, чтобы достичь правого нижнего угла. Таким образом, он не может сделать больше 2n ходов.
Давайте начнем с более простого случая: [найти все пути в правом нижнем углу]
Робот может точно choose(n,2n) = (2n)!/(n!*n!) Пути: ему нужно только выбрать, какой из 2n ходов будет правильным, а остальные - вниз (там ровно n из этих).
Чтобы сгенерировать возможные пути: просто сгенерируйте все двоичные векторы размером 2n с ровно n 1. 1 обозначает движение вправо, 0 - движение вниз.
Теперь давайте расширим его до всех путей:
Сначала выберите длину пути. Для этого переберите все возможности: 0 <= я <= 2n, где i - длина пути. В этом пути есть max(0,in) <= j <= min(i,n) правильных шагов.
Чтобы сгенерировать все возможности, используйте следующий псевдокод:
for each i in [0,2n]:
for each j in [max(0,i-n),min(i,n)]:
print all binary vectors of size i with exactly j bits set to 1
Примечание 1: печать всех двоичных векторов размера я с 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<String> robotPaths(int n){
List<String> pathList = new ArrayList<String>();
getPaths(n, 1,1, "", pathList);
return pathList;
}
public static void getPaths(int n, int i, int j, String path, List<String> 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 (i.e. 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 нулевая индексированная матрица.
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, ""));
}
}
Вот версия С# (только для справки), чтобы найти уникальные пути (обратите внимание, что это версия, которая возвращает количество путей с использованием динамического программирования (запоминание - ленивое) - Расчет количества ходов от верхнего левого угла до нижнего правого с движением в любом направлении) (более подробную информацию вы можете найти в моем блоге: http://codingworkout.blogspot.com/2014/08/robot-in-grid-unique-paths.html)
Tuple<int, int>[][] GetUniquePaths(int N)
{
var r = this.GetUniquePaths(1, 1, N);
return r;
}
private Tuple<int, int>[][] GetUniquePaths(int row, int column, int N)
{
if ((row == N) && (column == N))
{
var r = new Tuple<int, int>[1][];
r[0] = new Tuple<int, int>[] { new Tuple<int,int>(row, column) };
return r;
}
if ((row > N) || (column > N))
{
return new Tuple<int, int>[0][];
}
var uniquePathsByMovingDown = this.GetUniquePaths(row + 1, column, N);
var uniquePathsByMovingRight = this.GetUniquePaths(row, column + 1, N);
List<Tuple<int, int>[]> paths = this.MergePaths(uniquePathsByMovingDown,
row, column).ToList();
paths.AddRange(this.MergePaths(uniquePathsByMovingRight, row, column));
return paths.ToArray();
}
, где
private Tuple<int, int>[][] MergePaths(Tuple<int, int>[][] paths,
int row, int column)
{
Tuple<int, int>[][] mergedPaths = new Tuple<int, int>[paths.Length][];
if (paths.Length > 0)
{
Assert.IsTrue(paths.All(p => p.Length > 0));
for (int i = 0; i < paths.Length; i++)
{
List<Tuple<int, int>> mergedPath = new List<Tuple<int, int>>();
mergedPath.Add(new Tuple<int, int>(row, column));
mergedPath.AddRange(paths[i]);
mergedPaths[i] = mergedPath.ToArray();
}
}
return mergedPaths;
}
Тесты устройств
[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<int, int> 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<int, int> t in path)
{
Debug.Write(string.Format("({0}, {1}), ", t.Item1, t.Item2));
}
}
}
Вот полная реализация, которая работает как для прямоугольной, так и для квадратной сетки. Я оставлю вас, чтобы выяснить, как позаботиться о избытке "= > " в конце каждого пути.
import java.util.Arraylist;
public class PrintPath
{
static ArrayList<String> paths = new ArrayList<String>();
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();
}
}
Если вам просто нужно подсчитать допустимые пути:
Скажем, у вас есть матрица 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];
Быстрое размывание без рекурсии или раздутых структур данных.
ПРИМЕЧАНИЕ: это было удалено из-за дублирования, но поскольку это лучший поток в этом разделе, я удалил свой ответ из другого места и добавлю это здесь.
Ниже приведен код 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<N;i++)
{
arr[N-1][i]=1;
arr[i][N-1]=1;
}
for(int i = N-2;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];
}