Cuente las escaleras únicas a las que se puede llegar moviéndose un número dado de pasos hacia adelante o hacia atrás

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *