Dados dos puntos (x1, y1) y (x2, y2) en un sistema de coordenadas 2-D. La tarea es contar todos los caminos cuya distancia es igual a la distancia de Manhattan entre ambos puntos dados.
Ejemplos:
Entrada: x1 = 2, y1 = 3, x2 = 4, y2 = 5
Salida: 6
Entrada: x1 = 2, y1 = 6, x2 = 4, y2 = 9
Salida: 10
Enfoque: La distancia Manhattan entre los puntos (x1, y1) y (x2, y2) será abs(x1 – x2) + abs(y1 – y2)
Sea abs(x1 – x2) = m y abs(y1 – y2) = n
Todo camino con distancia igual a la distancia Manhattan siempre tendrá m + n aristas, m horizontales y n verticales. Por lo tanto, este es un caso básico de combinatoria que se basa en la formación de grupos. La idea detrás de esto es la cantidad de formas en que (m + n) cosas diferentes se pueden dividir en dos grupos, uno que contiene m elementos y el otro que contiene n elementos, que está dado porm + n C n es decir (m + n)! / m! * n! .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
// Function to return the value of nCk
ll binomialCoeff(int n, int k)
{
ll res = 1;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate value of
// [n * (n-1) *---* (n-k+1)] /
// [k * (k-1) *---* 1]
for (int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
// Function to return the number of paths
ll countPaths(int x1, int y1, int x2, int y2)
{
// Difference between the 'x'
// coordinates of the given points
int m = abs(x1 - x2);
// Difference between the 'y'
// coordinates of the given points
int n = abs(y1 - y2);
return (binomialCoeff(m + n, n));
}
// Driver code
int main()
{
int x1 = 2, y1 = 3, x2 = 4, y2 = 5;
cout << countPaths(x1, y1, x2, y2);
return 0;
}
Java
// Java implementation of the approach
class GfG
{
//static long ll long long int
// Function to return the value of nCk
static long binomialCoeff(int n, int k)
{
long res = 1;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate value of
// [n * (n-1) *---* (n-k+1)] /
// [k * (k-1) *---* 1]
for (int i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
}
return res;
}
// Function to return the number of paths
static long countPaths(int x1, int y1, int x2, int y2)
{
// Difference between the 'x'
// coordinates of the given points
int m = Math.abs(x1 - x2);
// Difference between the 'y'
// coordinates of the given points
int n = Math.abs(y1 - y2);
return (binomialCoeff(m + n, n));
}
// Driver code
public static void main(String[] args)
{
int x1 = 2, y1 = 3, x2 = 4, y2 = 5;
System.out.println(countPaths(x1, y1, x2, y2));
}
}
// This code is contributed by
// Prerna Saini.
Python3
# Python3 implementation of the approach # Function to return the value of nCk def binomialCoeff(n, k): res = 1 # Since C(n, k) = C(n, n-k) if (k > n - k): k = n - k # Calculate value of # [n * (n-1) *---* (n-k+1)] / # [k * (k-1) *---* 1] for i in range(k): res *= (n - i) res //= (i + 1) return res # Function to return the number # of paths def countPaths(x1, y1, x2, y2): # Difference between the 'x' # coordinates of the given points m = abs(x1 - x2) # Difference between the 'y' # coordinates of the given points n = abs(y1 - y2) return (binomialCoeff(m + n, n)) # Driver code x1, y1, x2, y2 = 2, 3, 4, 5 print(countPaths(x1, y1, x2, y2)) # This code is contributed # by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the value of nCk
static long binomialCoeff(int n, int k)
{
long res = 1;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate value of
// [n * (n-1) *---* (n-k+1)] /
// [k * (k-1) *---* 1]
for (int i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
}
return res;
}
// Function to return the number of paths
static long countPaths(int x1, int y1,
int x2, int y2)
{
// Difference between the 'x'
// coordinates of the given points
int m = Math.Abs(x1 - x2);
// Difference between the 'y'
// coordinates of the given points
int n = Math.Abs(y1 - y2);
return (binomialCoeff(m + n, n));
}
// Driver code
public static void Main()
{
int x1 = 2, y1 = 3, x2 = 4, y2 = 5;
Console.Write(countPaths(x1, y1, x2, y2));
}
}
// This code is contributed by
// Akanksha Rai
PHP
<?php
// PHP implementation of the approach
//static long ll long long int
// Function to return the value of nCk
function binomialCoeff($n, $k)
{
$res = 1;
// Since C(n, k) = C(n, n-k)
if ($k > $n - $k)
$k = $n - $k;
// Calculate value of
// [n * (n-1) *---* (n-k+1)] /
// [k * (k-1) *---* 1]
for ($i = 0; $i < $k; ++$i)
{
$res *= ($n - $i);
$res /= ($i + 1);
}
return $res;
}
// Function to return the number of paths
function countPaths($x1, $y1, $x2, $y2)
{
// Difference between the 'x'
// coordinates of the given points
$m =abs($x1 - $x2);
// Difference between the 'y'
// coordinates of the given points
$n = abs($y1 - $y2);
return (binomialCoeff($m + $n, $n));
}
// Driver code
{
$x1 = 2; $y1 = 3; $x2 = 4; $y2 = 5;
echo(countPaths($x1, $y1, $x2, $y2));
}
// This code is contributed by
// Code_Mech.
Javascript
<script>
// javascript implementation of the approach
// Function to return the value of nCk
function binomialCoeff(n, k)
{
var res = 1;
var i;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate value of
// [n * (n-1) *---* (n-k+1)] /
// [k * (k-1) *---* 1]
for (i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
// Function to return the number of paths
function countPaths(x1, y1, x2, y2)
{
// Difference between the 'x'
// coordinates of the given points
var m = Math.abs(x1 - x2);
// Difference between the 'y'
// coordinates of the given points
var n = Math.abs(y1 - y2);
return (binomialCoeff(m + n, n));
}
// Driver code
var x1 = 2, y1 = 3, x2 = 4, y2 = 5;
document.write(countPaths(x1, y1, x2, y2));
</script>
Producción:
6
Publicación traducida automáticamente
Artículo escrito por Mostafijur Rahaman y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA