机器人在网格中移动 [英] Robot moving in a grid

问题描述

机器人位于4x4网格的左上角.机器人可以向上，向下，向左或向右移动，但不能两次访问同一位置.机器人试图到达网格的右下角，它可以到达网格右下角的方式有多少种?

A robot is located at the top-left corner of a 4x4 grid. The robot can move either up, down, left, or right, but can not visit the same spot twice. The robot is trying to reach the bottom-right corner of the grid.The number of ways it can reach the bottom-right corner of the grid is?

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

Now i know that if the robot can only move down or right ,then the answer would be 8C4 because it has to go 4 squares to the right and 4 squares down, in any order.

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

But i am having difficulty in solving the problem when the robot can move both left and up!?

我只需要提示即可解决问题！我应该如何解决这个问题?

I just need a hint to solve the problem! How should i approach the problem?

推荐答案

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

You can write a recursive program that calculates all possible paths, and whenever it arrives at the down right corner it increments the number of paths. I wrote something, but I didn't test it. (Think of it as pseudocode to give you a start). Basically what this does, is call the moveRobot function on the current position (0, 0) with an empty field (the robot hasn't moved yet). Then it tries to move up, down, left and right. This movement is described in the respective functions. If one of these movements succeds(or more than one), the new position is marked in the field with a 1 instead of a 0. 1 means the robot has passed through that position. Then you call moveRobot again. This because in the new position you want to try all four movements once more.

主要功能:

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功能:

MoveRobot Function:

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;
    }
}

这篇关于机器人在网格中移动的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！