Count unique stairs that can be reached by moving given number of steps forward or backward | C ++ program for the above approach ; Function to count the number of unique stairs visited ; Checks whether the current stair is visited or not ; Store the possible moves from the current position ; Initialize a queue ; / Push the starting position ; Mark the starting position S as visited ; Iterate until queue is not empty ; Store the current stair number ; Pop it from the queue ; Check for all possible moves from the current stair ; Store the new stair number ; If it is valid and unvisited ; Push it into queue ; Mark the stair as visited ; Store the result ; Count the all visited stairs ; Print the result ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void countStairs ( int n , int x , int a , int b ) { int vis [ n + 1 ] = { 0 } ; int moves [ ] = { + a , - a , + b , - b } ; queue < int > q ; q . push ( x ) ; vis [ x ] = 1 ; while ( ! q . empty ( ) ) { int currentStair = q . front ( ) ; q . pop ( ) ; for ( int j = 0 ; j < 4 ; j ++ ) { int newStair = currentStair + moves [ j ] ; if ( newStair > 0 && newStair <= n && ! vis [ newStair ] ) { q . push ( newStair ) ; vis [ newStair ] = 1 ; } } } int cnt = 0 ; for ( int i = 1 ; i <= n ; i ++ ) if ( vis [ i ] == 1 ) cnt ++ ; cout << cnt ; } int main ( ) { int N = 10 , S = 2 , A = 5 , B = 7 ; countStairs ( N , S , A , B ) ; return 0 ; }