如果只能在3个方向上移动，如何找到机器人的路径：向右，向下，对角向下。 [英] How to find the path of robot if it can only move in 3 directions:right, down, diagonally down.

问题描述

想象一下，机器人坐在NxN网格的左上角。机器人只能向三个方向移动：向右，向下和对角向下。机器人必须到达NxN网格的右下角。想象一下，某些方块是禁区或偏移，这样机器人就无法踩到它们。编写一个程序来确定机器人可能的路径数。当用户输入坐标为（-1，-1）时，偏移点的输入结束。

输入：

输入网格尺寸

3

输入偏移的网格点数

0 1

-1 -1

输出：

机器人的路径是

Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in three directions: right , down and diagonally down. The robot has to reach the lower right hand corner of the NxN grid. Imagine certain squares are "off limits" or "offsets", such that the robot cannot step on them. Write a program to determine the number of possible paths for the robot.The entry of offset points ends when the user enters the coordinates as (-1,-1).
Input:
Enter the size of the grid
3
Enter the grid points that are offsets
0 1
-1 -1
output:
The paths for the robot are

( 0 , 0 ) - ( 1 , 0 ) - ( 2 , 0 ) - ( 2 , 1 ) - ( 2 , 2 )
( 0 , 0 ) - ( 1 , 0 ) - ( 1 , 1 ) - ( 2 , 1 ) - ( 2 , 2 )
( 0 , 0 ) - ( 1 , 0 ) - ( 1 , 1 ) - ( 1 , 2 ) - ( 2 , 2 )
( 0 , 0 ) - ( 1 , 0 ) - ( 1 , 1 ) - ( 2 , 2 )
( 0 , 0 ) - ( 1 , 0 ) - ( 2 , 1 ) - ( 2 , 2 )
( 0 , 0 ) - ( 1 , 1 ) - ( 2 , 1 ) - ( 2 , 2 )
( 0 , 0 ) - ( 1 , 1 ) - ( 1 , 2 ) - ( 2 , 2 )
( 0 , 0 ) - ( 1 , 1 ) - ( 2 , 2 )

我尝试过：

What I have tried:

#include <iostream>
using namespace std;
int numberOfPaths(int m, int n)
{
	int count[m][n];
	for (int i = 0; i < m; i++)
		count[i][0] = 1;
        for (int j = 0; j < n; j++)
		count[0][j] = 1;
	for (int i = 1; i < m; i++)
	{
		for (int j = 1; j < n; j++)
                   count[i][j] = count[i-1][j] + count[i][j-1]; 
	}
	return count[m-1][n-1];
}
int main()
{
	cout << numberOfPaths(3, 3);
	return 0;
}

//这是我发现如果它只能在2个方向上移动的路径：右，下。

//This is what I found to count the path if it can move only in 2 directions:right,down.

推荐答案

看起来需要学习一些分析方法。

你需要按顺序进行

Looks like to need to learn some analyze methods.
You need to proceed in order

引用：

想象一下，机器人坐在NxN网格的左上角。

机器人必须到达右下角NxN网格。

想象某些方块是禁区或偏移，这样机器人就无法踩到它们。

Imagine a robot sitting on the upper left hand corner of an NxN grid.
The robot has to reach the lower right hand corner of the NxN grid.
Imagine certain squares are "off limits" or "offsets", such that the robot cannot step on them.

你需要一个网格大小NxN，你会记住不受限制的位置。

You need a grid of size NxN where you will remember positions that are off limits.

引用：

机器人只能向三个方向移动：向右，向下和对角向下。

编写程序以确定机器人的可能路径数。

The robot can only move in three directions: right , down and diagonally down.
Write a program to determine the number of possible paths for the robot.

您需要计算所有路径。这意味着只要移动没有碰到网格边界或关闭限制位置，机器人就可以选择3个方向中的一个。

这是一个典型的递归问题：你需要写具有实际位置的函数，如果位置是最终位置，则它是新路径，否则对于每个移动，您检查是否允许移动，如果允许，则使用新位置调用此相同函数。

要么使用显式递归函数，要么使用回溯使用隐式递归。

我们不做你的HomeWork。

HomeWork不会测试你的乞讨技巧其他人做你的工作，它会让你思考并帮助你的老师检查你对你所学课程的理解，以及你应用它们时遇到的问题。

你的任何失败都会帮助你的老师发现你的弱点并设定补救措施。

你的任何失败都会帮助你了解什么有效，什么无效，被称为'试错'学习。



作为程序员，你的工作是创建算法来解决具体问题你不能依靠别人为你永远做到这一点，所以有一段时间你必须学习如何。

创建一个算法基本上是找到数学并做出必要的调整以适应你的实际问题。

You need to count all paths. which means that the robot can choose one of the 3 directions as long as the move do not hit a border of the grid or an off limit position.
This is a typical recursive problem: you need to write a function with actual position, if position is final position, it is a new path, otherwise for each moves, you check if move is allowed, and if allowed, call this same function with new position.
Either you do it with an explicit recursive function, or with implicit recursion using backtracking.
We do not do your HomeWork.
HomeWork is not set to test your skills at begging other people to do your work, it is set to make you think and to help your teacher to check your understanding of the courses you have taken and also the problems you have at applying them.
Any failure of you will help your teacher spot your weaknesses and set remedial actions.
Any failure of you will help you to learn what works and what don't, it is called 'trial and error' learning.

As programmer, your job is to create algorithms that solve specific problems and you can't rely on someone else to eternally do it for you, so there is a time where you will have to learn how to.
Creating an algorithm is basically finding the maths and make necessary adaptation to fit your actual problem.

（0,0） - （1,1） - （1,2） - （2,2）



（0,0） - （1,1） - （2,2）

( 0 , 0 ) - ( 1 , 1 ) - ( 1 , 2 ) - ( 2 , 2 )

( 0 , 0 ) - ( 1 , 1 ) - ( 2 , 2 )

这篇关于如果只能在3个方向上移动，如何找到机器人的路径：向右，向下，对角向下。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！