Hackerearth dfs problem

Can any one explain the logic given in editorial https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/practice-problems/algorithm/gudi-trapped-in-the-room-july-easy/


problem link not working please fix that first.

Copy paste to your browser and remove the square bracket at end of link. Should work like a charm! :slight_smile: (This error happens quite often XD)

1 Like

This is the working link

I want to ask a question please upvote me.


Here is logic of how we can solve this problem.
As it is mentioned in the question itself that “We can apply spell any number of times in any order”,We have to try for every possible string and first apply only H number of shifts and then apply dfs if it has n’t been applied for the string before,It will try for every string when shift operations has been applied first and then add A to even positions of string and then apply dfs if it has n’t been applied before for that string,This will try for every string when add operation has been applied.In this way we are making operations to the string with every possible way and checking for lexicographically smallest string.
Here is the code for reference Click Here


Why you are rotating string in anti-clock wise it is given in clockwise

Its clockwise s=987654 and H=2 becomes 549876.