Написать код на языке С для задачи
2000 UAH
The task of the competition assignment is to develop an efficient program that can solve the "rectangles" puzzle.
The puzzle is introduced into a rectangular field. The field contains empty spaces and spaces with numerical information. The task is to divide the entire area of the entered puzzle into rectangles such that:
- the rectangles cover the entire specified area,
- the rectangles do not overlap,
- each filled box is in a different rectangle,
- the size of the rectangle (area) equals the number of the filled square.
In solving, you know that the playing area has a size of no more than 32x32 squares, the total number of filled squares is no more than 200, and the filled numbers range from 1 to 99.
The program receives the input puzzle from standard input, and the input ends with the end of std. input (EOF is active). The exact format of the input can be seen in the example below.
The program analyzes the entered puzzle and determines which of the options has occurred:
- the input is invalid
- the input was a puzzle that has only one valid solution. In this case, the program will display this solution.
- The input was a puzzle that could not be assembled (0 solutions). The program outputs information about the failed attempt.
- The specified puzzle has many solutions (more than one), in this case, the program calculates how many ways the area can be divided. Different ways of division mean that the distribution of separating rectangles differs in the arrangement of at least one boundary line.
The program must check the correctness of the entered data. If the input data contains incorrect, nonsensical, or contradictory values, the program detects this, displays an error message, and terminates. The format of the error message is shown in the example execution below. An error is considered:
- missing, incorrect, or incomplete frame of the field,
- the content of the field differs from spaces and numbers 1-99,
- absence of corner box markings,
- array larger than 32 x 32,
- the number of filled fields exceeds 200.
The program is tested in a limited environment. It is limited by the amount of available memory and execution time. Both limitations can be seen in the solution testing log of the sample. Overall, the task does not require memory. However, it is very demanding on processor time. If the puzzle has multiple solutions, exploring all options can take a very long time. It is necessary to develop an efficient algorithm that avoids wasting time on attempts that do not lead to the goal.
The work is evaluated in a competitive mode. This means that it is more challenging than standard tasks. It requires a combination of programming and algorithmization skills. It is assumed that the tasks will be solved by students who have certain programming knowledge, i.e., students for whom standard tasks are boring. The evaluation consists of a guaranteed set of points (success in non-competitive tests) and a set of points earned for placement in the competition with other students (these points are credited after the competition ends).
Example of program work:
Enter the puzzle:
+--+--+--+--+--+
| 2 3 2|
+ + + + + +
| 2 3 |
+ + + + + +
| 3 |
+ + + + + +
| 2 |
+ + + + + +
| 2 3 3|
+--+--+--+--+--+
One solution:
+--+--+--+--+--+
| 2| 3 | 2|
+ +--+--+--+ +
| | 2| 3| |
+--+--+--+ +--+
| 3 | | |
+--+--+--+ + +
| | 2| | |
+ +--+--+--+ +
| 2| 3| 3|
+--+--+--+--+--+
Enter the puzzle:
+--+--+--+--+--+--+--+--+--+--+
| 4 2 |
+ + + + + + + + + + +
| 3 |
+ + + + + + + + + + +
| 2 3 8 |
+ + + + + + + + + + +
| 4 2 10 |
+ + + + + + + + + + +
| 2 2 3 |
+ + + + + + + + + + +
| 2 6|
+ + + + + + + + + + +
| 12 6 |
+ + + + + + + + + + +
| 2 4 4|
+ + + + + + + + + + +
| 10 3 |
+ + + + + + + + + + +
| 2 2 2 |
+--+--+--+--+--+--+--+--+--+--+
One solution:
+--+--+--+--+--+--+--+--+--+--+
| 4| 2| | | | | | |
+ + + + + + + + + + +
| | | | 3| | | | |
+ +--+ + + + + + + + +
| | 2| | | 3| 8| | |
+ + + +--+--+ + + + + +
| | | 4| 2 | | 10| |
+--+--+--+--+--+--+--+ + + +
| 2| 2| 3 | | |
+--+--+--+--+--+--+--+--+--+ +
| | | 2| 6|
+ + + + + + + + + +--+
| 12| 6 | | |
+--+--+--+--+--+--+ + +--+ +
| 2 | 4 | | | 4|
+--+--+--+--+--+--+--+--+ + +
| | | | 10 | 3| |
+ + + + + + + + + + +
| 2| 2| 2| | | |
+--+--+--+--+--+--+--+--+--+--+
Enter the puzzle:
+--+--+--+--+--+--+--+--+--+
| 2 3 2 |
+ + + + + + + + + +
| 3 2 2 1 |
+ + + + + + + + + +
| 7 |
+ + + + + + + + + +
| 7 3 |
+ + + + + + + + + +
| 4 4 3 3 7|
+ + + + + + + + + +
| 3 |
+ + + + + + + + + +
| 4 3 |
+--+--+--+--+--+--+--+--+--+
One solution:
+--+--+--+--+--+--+--+--+--+
| 2| 3| | | 2 | |
+ +--+--+--+ + +--+--+ +
| | 3| 2| 2| 1| | |
+--+--+--+--+--+--+--+ + +
| 7 | | |
+--+--+--+--+--+--+--+ + +
| 7 | 3| |
+--+--+--+--+--+--+--+--+ +
| 4| 4| 3| 3 | 7|
+ + + + + +--+--+--+ +
| | | | 3 | |
+--+--+--+--+ +--+--+--+ +
| 4 | | 3 | |
+--+--+--+--+--+--+--+--+--+
Enter the puzzle:
+--+--+--+--+
| 4 |
+ + + + +
| 4 |
+ + + + +
| 4 |
+ + + + +
| 4|
+--+--+--+--+
Total solutions: 9
Enter the puzzle:
+--+--+--+--+--+--+--+--+--+
| 3 3 |
+ + + + + + + + + +
| 4 4 3 2 2 3 |
+ + + + + + + + + +
| 2 |
+ + + + + + + + + +
| 4 2 3 |
+ + + + + + + + + +
| 3 6 |
+ + + + + + + + + +
| 2 2 2 |
+ + + + + + + + + +
| 2 2 2 8|
+ + + + + + + + + +
| 8 |
+--+--+--+--+--+--+--+--+--+
Total solutions: 39
Enter the puzzle:
+--+--+--+--+--+--+
| |
+ + + + + + +
| 12 |
+ + + + + + +
| 2 4 |
+ + + + + + +
| 4 |
+ + + + + + +
| 2 |
+ + + + + + +
| |
+ + + + + + +
| 2 8 |
+ + + + + + +
| 3 5 6|
+--+--+--+--+--+--+
No solution.
Enter the puzzle:
+--+--+--+--+--+
| 2 |
+ + + + + +
| 3 2 |
+ + + + + +
| 3 |
+ + + + + +
| |
+ + + + + +
| 2 2 7|
+ + + + + +
| 3 |
+ + + + + +
| 2 7 2 |
+--+--+--+--+--+
Bad input.
-
Добрий день. А приклад виконавчої роботи правильно вставився, враховуючи усі відступи? А то не зовсім розумію... Може ви можете прислати безпосередньо файл із завданням?
-
Украина