Minimum circular rotations to obtain a given numeric string by avoiding a set of given strings | C ++ Program to count the minimum number of circular rotations required to obtain a given numeric strings avoiding a set of blocked strings ; If the starting string needs to be avoided ; If the final string needs to be avoided ; Variable to store count of rotations ; BFS Approach ; Store the current size of the queue ; Traverse the string ; Increase the current character ; Circular rotation ; If target is reached ; If the string formed is not one to be avoided ; Add it to the list of strings to be avoided to prevent visiting already visited states ; Decrease the current value by 1 and repeat the similar checkings ; Restore the original character ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minCircularRotations ( string target , vector < string > & blocked , int N ) { string start = " " ; for ( int i = 0 ; i < N ; i ++ ) { start += '0' ; } unordered_set < string > avoid ; for ( int i = 0 ; i < blocked . size ( ) ; i ++ ) avoid . insert ( blocked [ i ] ) ; if ( avoid . find ( start ) != avoid . end ( ) ) return -1 ; if ( avoid . find ( target ) != avoid . end ( ) ) return -1 ; queue < string > qu ; qu . push ( start ) ; int count = 0 ; while ( ! qu . empty ( ) ) { count ++ ; int size = qu . size ( ) ; for ( int j = 0 ; j < size ; j ++ ) { string st = qu . front ( ) ; qu . pop ( ) ; for ( int i = 0 ; i < N ; i ++ ) { char ch = st [ i ] ; st [ i ] ++ ; if ( st [ i ] > '9' ) st [ i ] = '0' ; if ( st == target ) return count ; if ( avoid . find ( st ) == avoid . end ( ) ) qu . push ( st ) ; avoid . insert ( st ) ; st [ i ] = ch - 1 ; if ( st [ i ] < '0' ) st [ i ] = '9' ; if ( st == target ) return count ; if ( avoid . find ( st ) == avoid . end ( ) ) qu . push ( st ) ; avoid . insert ( st ) ; st [ i ] = ch ; } } } return -1 ; } int main ( ) { int N = 4 ; string target = "7531" ; vector < string > blocked = { "1543" , "7434" , "7300" , "7321" , "2427" } ; cout << minCircularRotations ( target , blocked , N ) << endl ; return 0 ; }