Import java.util.
*;
Public class DanceRevolution {
Static class State {
String foot1; // First foot position
String foot2; // Second foot position
Int moves; // Total moves to reach this state
Int index; // Current instruction index
State(String foot1, String foot2, int moves, int index) {
This.foot1 = foot1;
This.foot2 = foot2;
This.moves = moves;
This.index = index;
Public static int minMoves(int N, String[] instructions) {
String[] tiles = {“up”, “down”, “left”, “right”};
Queue<State> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
// Initialize BFS with all possible starting positions
For (String foot1 : tiles) {
For (String foot2 : tiles) {
If (!foot1.equals(foot2)) {
Queue.add(new State(foot1, foot2, 0, 0));
Visited.add(foot1 + “,” + foot2 + “,0”);
// BFS Loop
While (!queue.isEmpty()) {
State current = queue.poll();
// If all instructions are processed, return the moves
If (current.index == N) {
Return current.moves;
String target = instructions[current.index]; // Current instruction
// Generate new states by moving foot1 or foot2 to the target
List<State> nextStates = new ArrayList<>();
If (!current.foot1.equals(target)) {
nextStates.add(new State(target, current.foot2, current.moves + 1, current.index +
1));
} else {
nextStates.add(new State(current.foot1, current.foot2, current.moves,
current.index + 1));
If (!current.foot2.equals(target)) {
nextStates.add(new State(current.foot1, target, current.moves + 1, current.index +
1));
} else {
nextStates.add(new State(current.foot1, current.foot2, current.moves,
current.index + 1));
// Process new states and add to the queue if not visited
For (State nextState : nextStates) {
String key = nextState.foot1 + “,” + nextState.foot2 + “,” + nextState.index;
If (!visited.contains(key)) {
Queue.add(nextState);
Visited.add(key);
Return -1; // This line will never be reached for valid inputs
Public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// Input
Int N = scanner.nextInt();
Scanner.nextLine(); // Consume the newline
String[] instructions = new String[N];
For (int I = 0; I < N; i++) {
Instructions[i] = scanner.nextLine();
// Output
System.out.println(minMoves(N, instructions));
