4.md

Task 4: Quantum Maze

File with basic solution

File with advanced solution

There is a maze with the following characters: . - no obstacles X - obstacle ? - obstacle in superposition S - start E - end

Obstacles in superposition have a 50% probability. This means that with a 50% chance you can pass through this obstacle. If you pass through two such obstacles, the probability will be 25%. You can move in all directions, including diagonal movements.

1. If there is a path with a 100% probability of passing (without obstacles in superposition), then find the shortest such path.
2. If there is no path with a 100% probability of passing, then you need to find the shortest path with the highest probability. Thus, the priority is the probability of passing.
3. If there is no path, then return null.

Solution of this task must be implemented in the GET function (int, int, int, tuple) solve_maze(int n, int m, tuple maze):

• in this version of the task always -1;
• probability of passing the path;
• path length;
• maze with path or null if there is none.

Advanced Version

If there is no path, then you need to change the minimum number of X so that the path appears. The main factor is the minimum number of changes X. Also, if the minimum change X creates several paths, choose the path with the highest probability. If the probabilities are the same, then you need to choose the path with the shortest length.

Solution of this task must be implemented in the GET function (int, int, int, tuple) solve_maze(int n, int m, tuple maze):

• minimum number of changes X;
• number of passed obstacles in superposition;
• path length;
• maze with path or null if there is none.

Additionally

• If identical paths are found by probability and length in both versions of the problem, return any of them.
• The maze will be passed without spaces.
• The maze can have a rectangular shape.
• The path taken must be indicated by the symbol !. It is also necessary to return the probability of passing (see below) and the length of the path.
• Since it will be difficult to correctly calculate the percentages in integer calculations, it is necessary to return only the number of passed obstacles in superposition.
• If there is no path, then all int values must be equal to 0 (except -1 in basic version).
• Gas limit of TVM is increased to 0.1 TON in tests.
• Minimum maze size is 2x2.
• Maximum maze size is 8x8 for basic version and 31x31 for advanced version
• It is guaranteed that the maze will be correct (one start and one end).

Examples

Example 1

Maze

X	X	X	X	X	X	E	.
X	X	.	X	X	X	X	.
X	.	X	.	X	X	X	X
.	?	X	S	X	X	X	.
?	.	X	X	X	X	X	.
X	X	.	.	X	X	X	.
X	X	.	.	X	X	?	X
X	X	X	.	.	.	X	X

Solved maze

X	X	X	X	X	X	E	.
X	X	!	X	X	X	X	!
X	!	X	!	X	X	!	X
!	?	X	S	X	X	X	!
?	!	X	X	X	X	X	!
X	X	!	.	X	X	X	!
X	X	.	!	X	X	!	X
X	X	X	.	!	!	X	X

or null in basic version

• Obstacles to break: 1 (-1 in basic version)
• Obstacles in superposition: 1 (0 in basic version)
• Distance: 16 (0 in basic version)

Example 2

Maze

S	X	.	?	X
.	X	X	.	X
X	.	?	.	.
.	?	?	.	.
X	?	.	.	.
.	.	X	.	X
.	.	?	.	.
X	.	.	.	E

Solved maze

S	X	.	?	X
!	X	X	.	X
X	!	?	.	.
.	!	?	.	.
X	?	!	.	.
.	.	X	!	X
.	.	?	!	.
X	.	.	.	E

• Obstacles to break: 0 (-1 in basic version)
• Obstacles in superposition: 1
• Distance: 7

Solution evaluation

There will be two groups of tests:

1. Will check only the first part of the task. For a full solution - 3 points.
2. Will check the task taking into account the additional part. For a solution - 4 points, additionally 1 point for gas.

You can not solve the basic version of this task if you solved the advanced one. Thus, if task4basic.fc will be empty, but task4.fc will have a working solution, then you will get 3 + 4 + n points, where n is the number of points for gas.