algorithm - 机器人在网格中移动

Question

机器人位于 4x4 网格的左上角。机器人可以上下左右移动，但不能两次访问同一地点。机器人试图到达网格的右下角。它可以到达网格右下角的方式有多少？

现在我知道如果机器人只能向下或向右移动，那么答案将是 8C4，因为它必须以任意顺序向右移动 4 格，向下移动 4 格。

但是当机器人可以左右移动时，我很难解决问题！？

我只需要一个提示来解决问题！我应该如何解决这个问题？

Answer 1

这将正常工作。答案是 184。

public class RobotMovementProblem 
{
    public static void main(String[] args) 
    {
        int grid[][]=new int[4][4];
        System.out.println(countPaths(grid, 0, 0));
    }
    static int countPaths(int grid[][],int i,int j)
    {

        if ( i < 0 || j < 0 || i >= 4 || j >= 4 ) return 0;
        if ( grid[i][j] == 1 ) return 0;
        if ( i == 3 && j == 3 ) return 1;
        int arr[][]=new int[4][4];
        for(int m=0;m<4;m++)
        {
            for(int n=0;n<4;n++)
            {
                arr[m][n]=grid[m][n];
            }
        }

        arr[i][j] = 1;
        return countPaths(arr, i, j+1) + countPaths(arr, i, j-1) +  countPaths(arr, i+1, j) + countPaths(arr, i-1, j);  
    }
}

Answer 2

您可以编写一个递归程序来计算所有可能的路径，并且每当它到达右下角时，它就会增加路径的数量。我写了一些东西，但我没有测试它。（把它想象成伪代码给你一个开始）。基本上它的作用是在当前位置 (0, 0) 上调用 moveRobot 函数，并带有一个空字段（机器人尚未移动）。然后它尝试向上、向下、向左和向右移动。该运动在相应的功能中进行了描述。如果这些动作中的一个成功（或不止一个），则在字段中用 1 而不是 0 标记新位置。1 表示机器人已通过该位置。然后你再次调用 moveRobot。这是因为在新姿势中，您想再次尝试所有四个动作。

主功能：

int field[4][4];
for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
        field[i][j] = 0;
field[0][0] = 1;
numPaths = 0;
moveRobot(0, 0, field);
print numPaths;

移动机器人功能：

moveRobot(int row, int column, int[][] field)
{
    moveRobotUp(row, column, field);
    moveRobotDown(row, column, field);
    moveRobotLeft(row, column, field);
    moveRobotRight(row, column, field);
}

其他功能：

moveRobotUp(int row, int column, int[][] field)
{
    if (row == 0) return;
    else 
    {
        if (field[row-1][column] == 1) return;
        field[row-1][column] = 1;
        moveRobot(row-1, column, field);
        field[row-1][column] = 0;
    }
}

moveRobotDown(int row, int column, int[][] field)
{
    if (row == 3 && column == 3) 
    {
        numPaths++;
        return;
    }
    else if (row == 3) return;
    else
    {
        if (field[row+1][column] == 1) return;
        field[row+1][column] = 1;
        moveRobot(row+1, column, field);
        field[row+1][column] = 0;
    }
}

moveRobotLeft(int row, int column, int[][] field)
{
    if (column == 0) return;
    else
    {
        if (field[row][column-1] == 1) return;
        field[row][column-1] = 1;
        moveRobot(row, column-1, field);
        field[row][column-1] = 0;
    }
}

moveRobotRight(int row, int column, int[][] field)
{
    if (column == 3 && row == 3) 
    {
        numPaths++;
        return;
    }
    else if (column == 3) return;
    else 
    {
        if (field[row][column+1] == 1) return;
        field[row][column+1] = 1;
        moveRobot(row, column+1, field);
        field[row][column+1] = 0;
    }
}

Answer 3

/* building on red_eyes answer */

public static void main(String[] args) {
    Main m = new Main();
    boolean grid [][]= new boolean [4][4];
    sol=0;
    grid[0][0]= true;
    m.start(0,1,grid);
    System.out.println(sol);//output 184
}

    private void start(int x, int y,boolean [][]grid){
    grid[x][y]=true;
    moveUp(x,y,grid);
    moveDown(x,y,grid);     
    moveLeft(x,y,grid);     
    moveRight(x,y,grid);         
}

private void moveUp(int x, int y, boolean [][] grid){
    if(y==0) return;
    else{
        if (grid[x][y-1]) return;
        grid[x][y-1]=true;
        start(x,y-1,grid);
        grid[x][y-1]=false;
    }
}
   private void moveLeft(int x, int y, boolean [][] grid){
    if(x==0) return;
    else{
        if (grid[x-1][y]) return;
        grid[x-1][y]=true;
        start(x-1,y,grid);
        grid[x-1][y]=false; 
    }
}
private void moveDown(int x, int y, boolean [][] grid){
    if(x==3 && y==3){
        sol++;
        grid[x][y]=true;
        return;
    }
    else if(y==3) return;
    else{
        if (grid[x][y+1]) return;
        grid[x][y+1]=true;
        start(x,y+1,grid);
        grid[x][y+1]=false;
    }
}


private void moveRight(int x, int y, boolean [][] grid){
    if(x==3 && y==3){
        sol++;
        grid[x][y]=true;
        return;
    }else if(x==3) return;
    else{
        if (grid[x+1][y]) return;
        grid[x+1][y]=true;
        start(x+1,y,grid);
        grid[x+1][y]=false; 
    }
}

Answer 4

几行递归将解决这个问题。

    public static int WaysToExit(int x, int y)
    {
        if (x==0 || y == 0)
        {
            return 1;
        }
        else
        {
            return (WaysToExit(x - 1, y) + WaysToExit(x , y-1));
        }
    }