MAKE THIS TASK FASTER : N$=20$ FOR LESS THAN SECOND TO BE SOLVED

#include

#include

#include

#include

$//$ Helper function to check if we have reached the goal configuration

bool isGoal$($const std::string& state, int N$)\{$

std::string goal$($N$,\text{'}<\text{'})$; $//$ N frogs facing left

goal $+="\_"$; $//$ One empty space

goal $+=$ std::string$($N$,\text{'}>\text{'})$; $//$ N frogs facing right

return state $==$ goal;

$\}$

$//$ Helper function to generate all possible moves from a given state

std::vector generateMoves$($const std::string& state$)\{$

std::vector nextStates;

int size $=$ state.size$()$;

for $($int i $=0$; i $<$ size; $++$i$)\{$

if $($state$[$i$]==\text{'}>\text{'})\{$

$//$ Try to move right

if $($i $+1<$ size && state$[$i $+1]==\text{'}\_\text{'})\{$

std::string newState $=$ state;

std::swap$($newState$[$i$],$ newState$[$i $+1])$;

nextStates.push$\_$back$($std::move$($newState$))$;

$\}$

$//$ Try to jump over one frog

if $($i $+2<$ size && state$[$i $+2]==\text{'}\_\text{'}$ && state$[$i $+1]==\text{'}<\text{'})\{$

std::string newState $=$ state;

std::swap$($newState$[$i$],$ newState$[$i $+2])$;

nextStates.push$\_$back$($std::move$($newState$))$;

$\}$

$\}$

else if $($state$[$i$]==\text{'}<\text{'})\{$

$//$ Try to move left

if $($i $-1>=0$ && state$[$i $-1]==\text{'}\_\text{'})\{$

std::string newState $=$ state;

std::swap$($newState$[$i$],$ newState$[$i $-1])$;

nextStates.push$\_$back$($std::move$($newState$))$;

$\}$

$//$ Try to jump over one frog

if $($i $-2>=0$ && state$[$i $-2]==\text{'}\_\text{'}$ && state$[$i $-1]==\text{'}>\text{'})\{$

std::string newState $=$ state;

std::swap$($newState$[$i$],$ newState$[$i $-2])$;

nextStates.push$\_$back$($std::move$($newState$))$;

$\}$

$\}$

$\}$

return nextStates;

$\}$

$//$ Helper function to check if a state has been visited

bool isVisited$($const std::string& state, std::unordered$\_$set& visited$)\{$

return visited.find$($state$)!=$ visited.end$()$;

$\}$

$//$ Depth$-$First Search to find the solution

bool dfs$($const std::string& state, int N$,$ std::unordered$\_$set& visited, std::vector& solution$)\{$

$//$ Mark the current state as visited

visited.insert$($state$)$;

solution.push$\_$back$($state$)$;

$//$ Check if we have reached the goal configuration

if $($isGoal$($state$,$ N$))\{$

return true;

$\}$

$//$ Generate all possible next moves

std::vector nextStates $=$ generateMoves$($state$)$;

$//$ Perform DFS on each possible move

for $($const auto& nextState : nextStates$)\{$

if $(!$isVisited$($nextState$,$ visited$))\{$

if $($dfs$($nextState$,$ N$,$ visited, solution$))\{$

return true;

$\}$

$\}$

$\}$

$//$ Backtrack if no solution is found

solution.pop$\_$back$()$;

return false;

$\}$

int main$()\{$

int N;

std::cout $<<$ "Enter the number of frogs facing in each direction $($N$)$: $"$;

std::cin $>>$ N;

$//$ Initial state: N frogs facing right, one empty space, N frogs facing left

std::string initialState$($N$,\text{'}>\text{'})$;

initialState $+="\_"$;

initialState $+=$ std::string$($N$,\text{'}<\text{'})$;

$//$ Data structures to track visited states and the solution path

std::unordered$\_$set visited;

std::vector solution;

$//$ Perform DFS to find the solution

if $($dfs$($initialState$,$ N$,$ visited, solution$))\{$

$//$ Print the solution steps

std::cout $<<$ "Solution found:

$"$;

for $($const auto& step : solution$)\{$

std::cout $<<$ step $<<"$

$"$;

$\}$

$\}$

else $\{$

std::cout $<<"$No solution found.

$"$;

$\}$

return $0$;

$\}$