Dados dos enteros N y M , donde M y N denotan una array de dimensiones N * M que consta de 0 solamente. La tarea es minimizar el recuento de rutas únicas desde la parte superior izquierda (0, 0) hasta la parte inferior derecha (N – 1, M – 1) de la array a través de celdas que consisten solo en 0 colocando exactamente K 1 en la array.
Nota: Ni la celda inferior derecha ni la celda superior izquierda se pueden modificar a 0.
Ejemplos:
Entrada: N = 3, M = 3, K = 1
Salida: 2
Explicación:
Colocar K(= 1) 1s en la array para generar la array [[0, 0, 0], [0, 1, 0], [ 0, 0, 0]] deja solo dos caminos posibles desde la celda superior izquierda a la inferior derecha.
Los caminos son [(0, 0) → (0, 1) → (0, 2) → (1, 2) → (2, 2)] y [(0, 0) → (1, 0) → (2 , 0) → (2, 1) → (2, 2)]Entrada: N = 3, M = 3, K = 3
Salida : 0
Explicación:
Colocar K(= 3) 1 para generar una array [[0, 1, 1], [1, 0, 0], [0, 0 , 0]] no deja ningún camino posible de arriba a la izquierda a abajo a la derecha.
Enfoque: El problema se puede resolver considerando los siguientes casos posibles.
- Si K ≥ 2: La cuenta de caminos posibles se puede reducir a 0 colocando dos 1 en (0, 1) y (1, 0) celdas de la array.
- Si K = 0: La cuenta sigue siendo C(N+M-2, N-1).
- Si K = 1: coloque un 1 en el centro de la array, ((N-1)/2, (M-1)/2) para minimizar el recuento de rutas. Por lo tanto, el conteo de caminos posibles para este caso es el siguiente:
Resultado = Número total de formas de llegar al punto inferior derecho desde la parte superior izquierda – (Número de caminos al punto medio desde la parte superior izquierda * Número de formas de llegar al punto final desde el punto medio)
donde
- Número total de formas de llegar a la parte inferior derecha desde la parte superior izquierda = C (N + M – 2, N – 1)
- Número de caminos al punto medio desde la parte superior izquierda = C ((N – 1) / 2 + (M – 1) / 2, (N – 1) / 2)
- Número de formas de llegar al punto final desde el punto medio=C (((N – 1) – (N – 1 ) / 2) + ((M – 1) – (M – 1) / 2), ((N – 1) ) – (N – 1) / 2))
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the value of
// Binomial Coefficient C(n, k)
int ncr(int n, int k)
{
int res = 1;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate the 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 find the minimum
// count of paths from top
// left to bottom right by
// placing K 1s in the matrix
int countPath(int N, int M, int K)
{
int answer;
if (K >= 2)
answer = 0;
else if (K == 0)
answer = ncr(N + M - 2, N - 1);
else {
// Count of ways without 1s
answer = ncr(N + M - 2, N - 1);
// Count of paths from starting
// point to mid point
int X = (N - 1) / 2 + (M - 1) / 2;
int Y = (N - 1) / 2;
int midCount = ncr(X, Y);
// Count of paths from mid
// point to end point
X = ((N - 1) - (N - 1) / 2)
+ ((M - 1) - (M - 1) / 2);
Y = ((N - 1) - (N - 1) / 2);
midCount *= ncr(X, Y);
answer -= midCount;
}
return answer;
}
// Driver Code
int main()
{
int N = 3;
int M = 3;
int K = 1;
cout << countPath(N, M, K);
return 0;
}
Java
// Java Program to implement
// the above approach
import java.util.*;
class GFG{
// Function to return the value of
// Binomial Coefficient C(n, k)
static int ncr(int n, int k)
{
int res = 1;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate the 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 find the minimum
// count of paths from top
// left to bottom right by
// placing K 1s in the matrix
static int countPath(int N, int M, int K)
{
int answer;
if (K >= 2)
answer = 0;
else if (K == 0)
answer = ncr(N + M - 2, N - 1);
else
{
// Count of ways without 1s
answer = ncr(N + M - 2, N - 1);
// Count of paths from starting
// point to mid point
int X = (N - 1) / 2 + (M - 1) / 2;
int Y = (N - 1) / 2;
int midCount = ncr(X, Y);
// Count of paths from mid
// point to end point
X = ((N - 1) - (N - 1) / 2) +
((M - 1) - (M - 1) / 2);
Y = ((N - 1) - (N - 1) / 2);
midCount *= ncr(X, Y);
answer -= midCount;
}
return answer;
}
// Driver Code
public static void main(String[] args)
{
int N = 3;
int M = 3;
int K = 1;
System.out.print(countPath(N, M, K));
}
}
// This code is contributed by shikhasingrajput
Python3
#Python3 Program to implement #the above approach #Function to return the value of #Binomial Coefficient C(n, k) def ncr(n, k): res = 1 #Since C(n, k) = C(n, n-k) if (k > n - k): k = n - k #Calculate the 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 find the minimum #count of paths from top #left to bottom right by #placing K 1s in the matrix def countPath(N, M, K): answer = 0 if (K >= 2): answer = 0 elif (K == 0): answer = ncr(N + M - 2, N - 1) else: #Count of ways without 1s answer = ncr(N + M - 2, N - 1) #Count of paths from starting #point to mid point X = (N - 1) // 2 + (M - 1) // 2 Y = (N - 1) // 2 midCount = ncr(X, Y) #Count of paths from mid #point to end point X = ((N - 1) - (N - 1) // 2)+ ((M - 1) - (M - 1) // 2) Y = ((N - 1) - (N - 1) // 2) midCount *= ncr(X, Y) answer -= midCount return answer #Driver Code if __name__ == '__main__': N = 3 M = 3 K = 1 print(countPath(N, M, K)) # This code is contributed by Mohit Kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to return the value of
// Binomial Coefficient C(n, k)
static int ncr(int n, int k)
{
int res = 1;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate the 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 find the minimum
// count of paths from top
// left to bottom right by
// placing K 1s in the matrix
static int countPath(int N, int M, int K)
{
int answer;
if (K >= 2)
answer = 0;
else if (K == 0)
answer = ncr(N + M - 2, N - 1);
else
{
// Count of ways without 1s
answer = ncr(N + M - 2, N - 1);
// Count of paths from starting
// point to mid point
int X = (N - 1) / 2 + (M - 1) / 2;
int Y = (N - 1) / 2;
int midCount = ncr(X, Y);
// Count of paths from mid
// point to end point
X = ((N - 1) - (N - 1) / 2) +
((M - 1) - (M - 1) / 2);
Y = ((N - 1) - (N - 1) / 2);
midCount *= ncr(X, Y);
answer -= midCount;
}
return answer;
}
// Driver Code
public static void Main(String[] args)
{
int N = 3;
int M = 3;
int K = 1;
Console.Write(countPath(N, M, K));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript Program to implement
// the above approach
// Function to return the value of
// Binomial Coefficient C(n, k)
function ncr(n, k)
{
var res = 1;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate the value of
// [n * (n-1) *---* (n-k+1)] /
// [k * (k-1) *----* 1]
for (var i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
// Function to find the minimum
// count of paths from top
// left to bottom right by
// placing K 1s in the matrix
function countPath(N, M, K)
{
var answer;
if (K >= 2)
answer = 0;
else if (K == 0)
answer = ncr(N + M - 2, N - 1);
else {
// Count of ways without 1s
answer = ncr(N + M - 2, N - 1);
// Count of paths from starting
// point to mid point
var X = (N - 1) / 2 + (M - 1) / 2;
var Y = (N - 1) / 2;
var midCount = ncr(X, Y);
// Count of paths from mid
// point to end point
X = ((N - 1) - (N - 1) / 2)
+ ((M - 1) - (M - 1) / 2);
Y = ((N - 1) - (N - 1) / 2);
midCount *= ncr(X, Y);
answer -= midCount;
}
return answer;
}
// Driver Code
var N = 3;
var M = 3;
var K = 1;
document.write( countPath(N, M, K));
</script>
Producción:
2
Complejidad temporal: O(N+M)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por math_lover y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA