Dado un número entero N , que representa el número de escaleras, con un valor de 1 a N , y una posición inicial S , la tarea es contar el número máximo de escaleras únicas que se pueden alcanzar moviendo exactamente A o B pasos hacia adelante o hacia atrás desde cualquier posición, cualquier número de veces.
Ejemplos:
Entrada: N = 10, S = 2, A = 5, B = 7
Salida: 4
Explicación:
Posición inicial S: Escalera 2
Desde la Escalera 2, es posible llegar a las escaleras 7, es decir ( S + A ), y 9 , es decir (S + B).
Desde la Escalera 9, es posible llegar a la escalera 4, es decir (S – A).
Por lo tanto, el número único de escaleras que se pueden alcanzar es 4 {2, 4, 7, 9}.Entrada: N = 10, S = 2, A = 3, B = 4
Salida: 10
Enfoque: El problema dado se puede resolver utilizando la técnica transversal BFS . Siga los pasos a continuación para resolver el problema:
- Inicialice una cola y una array vis[] de tamaño (N + 1) e inicialícelo como falso .
- Marque el Node inicial S como visitado, es decir, vis[S] como 1 . Empuje S en una cola Q.
- Ahora itere hasta que Q no esté vacío y realice los siguientes pasos:
- Extraiga el elemento frontal de la cola y guárdelo en una variable, digamos currStair .
- Considere los 4 tipos posibles de movimientos de currStair, es decir , {+A, -A, +B, -B} .
- Para cada escalera nueva, verifique si es una escalera válida y no visitada o no. Si se encuentra que es cierto, entonces introdúzcalo en Q . Marque la escalera como visitada. De lo contrario, continúa .
- Finalmente, cuente el número de escaleras visitadas usando la array vis[] .
- Después de completar los pasos anteriores, imprima el recuento de escaleras visitadas como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the number
// of unique stairs visited
void countStairs(int n, int x, int a, int b)
{
// Checks whether the current
// stair is visited or not
int vis[n + 1] = { 0 };
// Store the possible moves
// from the current position
int moves[] = { +a, -a, +b, -b };
// Initialize a queue
queue<int> q;
/// Push the starting position
q.push(x);
// Mark the starting
// position S as visited
vis[x] = 1;
// Iterate until queue is not empty
while (!q.empty()) {
// Store the current stair number
int currentStair = q.front();
// Pop it from the queue
q.pop();
// Check for all possible moves
// from the current stair
for (int j = 0; j < 4; j++) {
// Store the new stair number
int newStair = currentStair + moves[j];
// If it is valid and unvisited
if (newStair > 0 && newStair <= n
&& !vis[newStair]) {
// Push it into queue
q.push(newStair);
// Mark the stair as visited
vis[newStair] = 1;
}
}
}
// Store the result
int cnt = 0;
// Count the all visited stairs
for (int i = 1; i <= n; i++)
if (vis[i] == 1)
cnt++;
// Print the result
cout << cnt;
}
// Driver Code
int main()
{
int N = 10, S = 2, A = 5, B = 7;
countStairs(N, S, A, B);
return 0;
}
Java
// Java program for the above approach
import java.util.LinkedList;
import java.util.Queue;
class GFG{
// Function to count the number
// of unique stairs visited
static void countStairs(int n, int x, int a, int b)
{
// Checks whether the current
// stair is visited or not
int[] vis = new int[n + 1];
// Store the possible moves
// from the current position
int[] moves = { +a, -a, +b, -b };
// Initialize a queue
Queue<Integer> q = new LinkedList<Integer>();
/// Push the starting position
q.add(x);
// Mark the starting
// position S as visited
vis[x] = 1;
// Iterate until queue is not empty
while (!q.isEmpty())
{
// Store the current stair number
int currentStair = q.peek();
// Pop it from the queue
q.remove();
// Check for all possible moves
// from the current stair
for(int j = 0; j < 4; j++)
{
// Store the new stair number
int newStair = currentStair + moves[j];
// If it is valid and unvisited
if (newStair > 0 && newStair <= n &&
vis[newStair] == 0)
{
// Push it into queue
q.add(newStair);
// Mark the stair as visited
vis[newStair] = 1;
}
}
}
// Store the result
int cnt = 0;
// Count the all visited stairs
for(int i = 1; i <= n; i++)
if (vis[i] == 1)
cnt++;
// Print the result
System.out.print(cnt);
}
// Driver Code
public static void main(String args[])
{
int N = 10, S = 2, A = 5, B = 7;
countStairs(N, S, A, B);
}
}
// This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach from collections import deque # Function to count the number # of unique stairs visited def countStairs(n, x, a, b): # Checks whether the current # stair is visited or not vis = [0] * (n + 1) # Store the possible moves # from the current position moves = [+a, -a, +b, -b] # Initialize a queue q = deque() # Push the starting position q.append(x) # Mark the starting # position S as visited vis[x] = 1 # Iterate until queue is not empty while (len(q) > 0): # Store the current stair number currentStair = q.popleft() # Pop it from the queue # q.pop() # Check for all possible moves # from the current stair for j in range(4): # Store the new stair number newStair = currentStair + moves[j] # If it is valid and unvisited if (newStair > 0 and newStair <= n and (not vis[newStair])): # Push it into queue q.append(newStair) # Mark the stair as visited vis[newStair] = 1 # Store the result cnt = 0 # Count the all visited stairs for i in range(1, n + 1): if (vis[i] == 1): cnt += 1 # Print the result print (cnt) # Driver Code if __name__ == '__main__': N, S, A, B = 10, 2, 5, 7 countStairs(N, S, A, B) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to count the number
// of unique stairs visited
static void countStairs(int n, int x,
int a, int b)
{
// Checks whether the current
// stair is visited or not
int []vis = new int[n + 1];
Array.Clear(vis, 0, vis.Length);
// Store the possible moves
// from the current position
int []moves = { +a, -a, +b, -b };
// Initialize a queue
Queue<int> q = new Queue<int>();
/// Push the starting position
q.Enqueue(x);
// Mark the starting
// position S as visited
vis[x] = 1;
// Iterate until queue is not empty
while (q.Count > 0)
{
// Store the current stair number
int currentStair = q.Peek();
// Pop it from the queue
q.Dequeue();
// Check for all possible moves
// from the current stair
for(int j = 0; j < 4; j++)
{
// Store the new stair number
int newStair = currentStair + moves[j];
// If it is valid and unvisited
if (newStair > 0 && newStair <= n &&
vis[newStair] == 0)
{
// Push it into queue
q.Enqueue(newStair);
// Mark the stair as visited
vis[newStair] = 1;
}
}
}
// Store the result
int cnt = 0;
// Count the all visited stairs
for(int i = 1; i <= n; i++)
if (vis[i] == 1)
cnt++;
// Print the result
Console.WriteLine(cnt);
}
// Driver Code
public static void Main()
{
int N = 10, S = 2, A = 5, B = 7;
countStairs(N, S, A, B);
}
}
// This code is contributed by ipg2016107
Javascript
<script>
// Javascript program for the above approach
// Function to count the number
// of unique stairs visited
function countStairs(n, x, a, b)
{
// Checks whether the current
// stair is visited or not
var vis = Array(n+1).fill(0);
// Store the possible moves
// from the current position
var moves = [ +a, -a, +b, -b ];
// Initialize a queue
var q = [];
/// Push the starting position
q.push(x);
// Mark the starting
// position S as visited
vis[x] = 1;
// Iterate until queue is not empty
while (q.length!=0) {
// Store the current stair number
var currentStair = q[0];
// Pop it from the queue
q.shift();
// Check for all possible moves
// from the current stair
for (var j = 0; j < 4; j++) {
// Store the new stair number
var newStair = currentStair + moves[j];
// If it is valid and unvisited
if (newStair > 0 && newStair <= n
&& !vis[newStair]) {
// Push it into queue
q.push(newStair);
// Mark the stair as visited
vis[newStair] = 1;
}
}
}
// Store the result
var cnt = 0;
// Count the all visited stairs
for (var i = 1; i <= n; i++)
if (vis[i] == 1)
cnt++;
// Print the result
document.write( cnt);
}
// Driver Code
var N = 10, S = 2, A = 5, B = 7;
countStairs(N, S, A, B);
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por single__loop y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA