Write a C++ program that accepts a FEN string (as described below), stores the piece location information in appropriate data structures, and then outputs the location of all pieces on the board, as well as the side whose move it is to play and then outputs the valid lion moves that can be made by whichever player it is to move. As a reminder, the lion moves as follows: Lion: The lion moves and captures one square in any direction (including diagonally), but it may not leave its 3x3 castle (highlighted In brown in the diagrams). However, there is one exception to this rule: a lion is allowed to move in a straight or diagonal line across the river if it is able to immediately capture the opposing lion. If a player's lion is captured, that player immediately loses the game. The diagram below shows the moves the white lion is able to make. 5 4 3 2 1 d (a) In the current position, White's lion on c3 can move to the squares marked by a red square or can capture Black's pawn on d2 (red circle). (b) Compared to the position on the left, the White lion on c3 can now also move across the river to capture the Black lion on e5 and win the game (red arrow)! The White lion could also potentially capture Black's lion anywhere along the c-file. Input The first line of input is N, the number of FEN strings that must be read in as input. N lines follow, with each line consisting of a single FEN string. You may assume that each FEN string is a valid position, and so will contain exactly one white lion and one black lion. Output For each FEN string i, output the location of all pieces on the board, output the valid lion moves. The moves should be printed in alphabetical order, and should be separated by a single space. Each move should be printed enter text. Jencoding described in move representations(i.e. as Sample Input 2 w 4 2elelz/ppppppp/7/7/7/PPP1PPP/2ELE1Z 1e1E12/P1P2P1/1P5/7/1E3P1/1P5/4L2 b 79 Sample Output d1d2 e7d6 e7d7 e7e1 e7e6 Visualisation of Above Test Cases 7 6 5 4 3 2 8 8 8 d e f 8 (a) The White lion can only move to d2, since it is blocked by its other pieces. a b 68 5 4 3 8 & GD 8 a b d e f 8 (b) The Black lion can move to the empty squares on d6 and e6 and can capture on d7. It cannot move to f7 or f6, since that would be outside of its 3 x 3 castle. It can also fly across the river to capture the white lion on el. Introduction In this section, we will develop a way of encoding the STATE of the game. A single state represents the current board position it should contain all the information necessary for the game (and successor function) to operate correctly. We will also need to generate the valid moves available to a player given the current state of the game. We will need to write code that accepts a game state as a FEN string and sets up the board. Once this has been done, the next step is to generate the moves available at the current position. This will depend on whether it is white or black to play. Forsyth-Edwards Notation Forsyth-Edwards Notation (FEN) is a standard way of encoding chess positions as a string. For the game Congo, the FEN string will consist of three fields, each separated by a blank space: Position of pieces In our FEN representation, we will specify the placement of each piece on the board. Each piece is encoded as a single character-white pieces uses capital letters, and black pieces use the corresponding lowercase letter. The pieces are: pawn (P), elephant (E), lion (L) and zebra (Z). ATB 4 3 2 & & & & & & & C a b C d e f g The starting position for White and Black The string describes each rank (row), starting from rank 7 to rank 1. The string for each rank specifies the location of a piece on that rank, and any number of empty squares. Each rank is separated by a . The easiest way to understand this encoding is to look at some examples, as illustrated below. Side to move The side to move is just a single character W or B that indicates whose turn it is to play Move number The move number records the number of moves played in the game. It is incremented only after black plays a move, and so a value of N indicates that both white and black have made w moves. 1. Position of pieces is a string that specifies the placement of each piece on the board. Each rank is described, starting from rank 7 and ending with rank 1. Move Representations For every submission, we will represent a move as a string specifying the starting location of the piece to move and then square the piece ends up on. For example, the move e3e4represents a piece moving from e3 to e4. intN; cin>>N; cin.ignore(); //NB! for(inti=0; i