Genetic Path Finder

Your task is to design a genetic algorithm that finds a valid path from the top-left corner to the bottom-right corner of a grid containing obstacles. The grid is given as an (n \times m) matrix where a cell with a value of 0 is free and a cell with a value of 1 is an obstacle. A candidate path is represented as a string of moves: 'U' (up), 'D' (down), 'L' (left), and 'R' (right). In a grid free of obstacles, a valid path contains exactly (n+m-2) moves consisting of exactly (n-1) moves down and (m-1) moves right. However, mutations during the evolution may produce moves in different directions. The fitness of a path is defined as the Manhattan distance from the endpoint reached by following the path to the destination, with the additional rule that if a move causes the path to enter an obstacle, its fitness is considered infinite. Your genetic algorithm should:

1. Generate an initial population of candidate paths.
2. Use crossover and mutation operations to evolve the population over a given number of generations.
3. Return the best valid path found, or an empty string if no valid path exists.

Note: All input must be read from standard input and the result must be printed to standard output. All formulas, such as (n+m-2), must be rendered in LaTeX format.

inputFormat

Input is provided via standard input. The first line contains two integers (n) and (m), representing the number of rows and columns. The next (n) lines each contain (m) integers (either 0 or 1) separated by spaces, representing the grid. The final line contains three values: population_size (an integer), mutation_rate (a float between 0 and 1), and generations (an integer).

outputFormat

Output a single line containing a string that represents the directions of the best path found. If no valid path exists, output an empty string.## sample

3 3
0 0 0
0 0 0
0 0 0
10 0.05 100

DDRR