Game of Life Reverse Engineering

**Task:** Implement a program in C that receives as input a state of the Game of Life (Conway's Game of Life) in a matrix of limited size and returns an immediately preceding state that minimizes the number of live cells in the matrix. **Specification:** The program should read a game state from the system’s standard input. An instance is given as a text file in the following format: - The first line of the file contains 2 integers, `n` and `m`, separated by a space, where `n` is the number of rows on the board and `m` is the number of columns. - The rest of the file contains `n` lines with `m` integers each, separated by spaces, where 0 represents a dead cell, and 1 represents a live cell. - All border cells of the matrix (first and last rows, first and last columns) are dead. - The example below represents a game instance with 4 rows and 6 columns: ``` 4 6 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 ``` The rules defining the evolution of one state to another in the game are: - Any dead cell with exactly three live neighbors becomes alive. - Any live cell with fewer than two live neighbors dies. - Any live cell with more than three live neighbors dies. - Any live cell with two or three live neighbors remains alive. These rules are applied simultaneously to all cells to reach the next game state. A cell's neighborhood consists of its 8 adjacent neighbors. For cells on the board’s edges, non-existent neighbors are considered dead. The objective of the program is to reverse the game, finding an immediately preceding state of the given input state. Furthermore, the preceding state must minimize the number of live cells in the matrix. The program’s output should be printed to the system’s standard output and must contain a matrix in the same format and size as the input, representing an immediately preceding state. Given the example above, a possible preceding state is: ``` 4 6 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 ``` Another possible preceding state is: ``` 4 6 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 ``` Considering the goal of minimizing the number of live cells, the first solution is more appropriate. **Evaluation Criteria:** - Strategy used. - Implementation quality and source code. - Performance in competition with other implementations. - The solution must solve an instance of the problem within a maximum time of 300 seconds and use no more than 8GB of memory. - Source code defense, if necessary. **Deadline:** Until 23:59 on 08/12/2024. The program should primarily use a heuristic-based algorithm to find the preceding state.