SOLVE THIS IN C$++$ : The game consists of a playing field with $2$N$+12$N $+12$N$+1$spaces$.$ Initially, on the rightmost NNN spaces, there are frogs facing left, and on the leftmost NNN spaces, there are frogs facing right. The goal of the game is for the frogs to swap places and reach the opposite configuration:

The rules of the game are as follows:

Each frog can move only in the direction it is facing.

Each frog can either jump to a free space directly in front of it or hop over one frog to land on a free space.

Use depth$-$first search $($DFS$)$to implement a program that solves the puzzle.

Input:

NNN: The number of frogs facing in one direction.

Output:

All configurations that lead from the initial state to the final state $($steps to solve the puzzle$).$

The task is expected to work for input N$=20$N $=20$N$=20$in less than $1$second$.$

Note: The puzzle can also be solved in linear time using a rule$-$based approach. You can attempt to solve it this way as well.

Example Input:

$$

$2$

Example Output:

php

$>\_<><\_>\_<>\_<><\_<>\_<\_><>\_<><\_>\_<\_<><>$

This is a frog$-$jumping puzzle where the objective is to swap two groups of frogs facing opposite directions. The task is to solve the puzzle using a DFS approach and print the steps of the solution. USE THIS GRAPH CONSTRUCTION:#include

#include

#include

#include

#include

class Graph

$\{$

int vertices;

std::vector$>$ adjList;

public:

Graph$($int vertices$)$ : vertices$($vertices$),$ adjList$($vertices$,$ std::vector$())\{\}$

Graph$($int vertices, std::vector$>$ edges$)$ : Graph$($vertices$)$

$\{$

int edgesCount $=$ edges.size$()$;

for $($int i $=0$; i $<$ edgesCount; i$++)$

$\{$

adjList$[$edges$[$i$].$first$].$push$\_$back$($edges$[$i$].$second$)$;

$\}$

$\}$

void BFS$($int start, std::vector& visited, int& sum, int& vertexCount$)$;

void DFS$($int start$)$;

void topologicalSort$()$;

private:

void DFSUtil$($int v$,$ std::vector& visited$)$;

void topologicalSortUtil$($int v$,$ std::vector& visited, std::stack& Stack$)$;

$\}$;

void Graph::DFS$($int start$)$

$\{$

std::vector visited$($vertices$,$ false$)$;

DFSUtil$($start$,$ visited$)$;

$\}$

void Graph::DFSUtil$($int v$,$ std::vector& visited$)$

$\{$

visited$[$v$]=$ true;

std::cout $<<$ v $<<""$;

for $($int neighbour : adjList$[$v$])$

$\{$

if $(!$visited$[$neighbour$])$

$\{$

DFSUtil$($neighbour$,$ visited$)$;

$\}$

$\}$

$\}$