Count points which are revisited while following the path specified by a given string | C ++ program for the above approach ; Function to find the number of times already visited position is revisited after starting traversal from { X , Y } ; Stores the x and y temporarily ; Stores the number of times an already visited position is revisited ; Initialize hashset ; Insert the starting coordinates ; Traverse over the string ; Update the coordinates according to the current directions ; If the new { X , Y } has been visited before , then increment the count by 1 ; Otherwise ; Insert new { x , y } ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int count ( string S , int X , int Y ) { int N = S . length ( ) ; int temp_x = 0 , temp_y = 0 ; int count = 0 ; set < pair < int , int > > s ; s . insert ( { X , Y } ) ; for ( int i = 0 ; i < N ; i ++ ) { temp_x = X ; temp_y = Y ; if ( S [ i ] == ' U ' ) { X ++ ; } else if ( S [ i ] == ' D ' ) { X -- ; } else if ( S [ i ] == ' R ' ) { Y ++ ; } else { Y -- ; } if ( s . find ( { temp_x + X , temp_y + Y } ) != s . end ( ) ) { count ++ ; } else { s . insert ( { temp_x + X , temp_y + Y } ) ; } } return count ; } int main ( ) { string S = " RDDUDL " ; int X = 0 , Y = 0 ; cout << count ( S , X , Y ) ; return 0 ; }