Lem-In

Description

Lem-in is an innovative and complex program designed to find solutions for optimization problems in graph theory. It simulates an anthill's room and tunnel structure and aims to move a certain number of ants from the start room to the end room in the minimum number of steps, all while adhering to specific constraints.

Utilizing an unoriented graph, the program reads the graph details and the number of ants from standard input, ensuring that each room (vertex) and tunnel (edge) only contain a single ant at a time.

Key Features

• Optimized Movement: Efficiently moves ants through the graph in the least amount of steps.

• Capacity Management: Ensures that each room (vertex) and tunnel (edge) only contain a single ant at a time.

• Step Management: Manages to move all possible ants simultaneously in a single "step" without violating the capacity constraints.

• Graph Reading: Reads and processes the graph details and number of ants from standard input.

File Specifications

The input file needs to follow specific rules:

• The rooms’ coordinates must be whole numbers.

• Comments and commands can be inserted by using “#” and “##” respectively.

• The next room after "##start" is considered the anthill entrance, and the next room after "##end" is considered the anthill exit.

• Any unknown commands will be ignored.

• The program stops reading the file after the first noncompliant or empty line and begins processing the data that has already been acquired.

The output follows a specific order: the number of ants, the rooms, the tunnels, and then for each lap, a series of "Pn-r", where "n" is the number of the ant and "r" is the name of the room it moves into.