Finding a way in the IOP labyrinth

Introduction and problem statement

We will denote the labyrinth by the abbreviation IOP, if it.

Rectangular and described by a size matrix $m\times n$ where in each cell (matrix cells) a sign of patency is encoded.
From each passage cell you can go to any adjacent passage cell vertically, horizontally, and along both diagonals, provided that the latter exists.

The cost of moving to an adjacent cell vertically or horizontally is . The cost of moving to an adjacent cell along any diagonal is equal to $\sqrt2$ .

We will call moving to an adjacent cell elementary movement.

Delivery of the task. Find the shortest path in a given maze between two passage cells of this maze. When finding a path, only integer variables can be used. Errors in calculations are not allowed. The algorithm should (at least in theory) work with arbitrarily large labyrinths.

Idea of solutions

To find the shortest path, you can use either the Bellman-Ford algorithm or the Dijkstra algorithm. Lee's algorithm (wave algorithm) is not suitable because it assumes that all edges of the graph have the same cost. The Floyd-Warshell algorithm for finding the shortest paths from each to each vertex will also theoretically work, but will require (at least in the worst case) $m^2 \times n^2$ memory for intermediate calculations and results.

So, as you can already guess, you need to come up with and program some type of data that will store distances.

Both algorithms involve the use of only two number operations.

Addition
Comparison

Note that the length of any path in such a labyrinth is always the sum of elementary movements along horizontals, verticals and diagonals.

If we sum up only the lengths of elementary movements along horizontals and verticals, we get a number of the form: Where – non-negative integer.

If we sum only the lengths of elementary movements along the diagonals, we get a number of the form: $b\sqrt2$ Where – non-negative integer.

Thus, the length of the entire path will be equal to the sum of these two numbers: $a+b\sqrt2$ . In what follows we will call such numbers composite. We will also call the corresponding data type composite number. Obviously, there will only be two values as fields of a composite number And .

For composite numbers, it is enough to implement the addition and comparison operations. If this can be done, then the above algorithms will be able to use composite numbers to solve the problem at hand: finding the shortest path.

Let's start analyzing the operations.

Addition

Formulation of the problem. Let there be two numbers: $c_1=a_1+b_1\sqrt2$ And $c_2=a_2+b_2\sqrt2$ Where – some integers. We need to find their sum: .

Solution. We find: $c=a_1+b_1\sqrt2+a_2+b_2\sqrt2=(a_1+a_2) + (b_1+b_2)\sqrt2$ . Thus, to find the sum, it is enough to simply add the corresponding parts of the original numbers.

Comparison

General Information and Helper Property

For both algorithms it is enough to implement more surgery. However, Dijkstra's algorithm for finding the unvisited vertex with the minimum path length can use priority queue instead of linear search. Whatever the type of element of such a queue, you must be able to compare it with another object of the same type. Often, a comparator is used for this, which can show how two objects relate. Such a comparator takes two objects and produces one of the following three values.

Less than: The first argument is less than the second (usually coded as )
Equal: the arguments are equal (usually coded as )
Greater than: the first argument is greater than the second (usually coded as )

We will consider the comparison of our two numbers “through the prism” of the implementation of such a comparator. In what follows, we will call the operation that such a comparator implements ratio operation and denoted by the symbol $\Leftrightarrow$ .

Let us introduce the unary operation inverting the result relation operations. We show what results from its application in the following table.

Result of the ratio operation	Inverting the result relation operations
Less	More
Equals	Equals
More	Less

When encoding the result with the above values, the operation of inverting the result of the ratio operation is nothing more than the operation unary minus. Therefore, for brevity, we will call it unary minus and denoted by the sign –.

As part of the task that will be posed below, it will be necessary to solve 4 inequalities $(>,<,\leq, \geq)$ and equation. In order to generalize these solutions, we move from solving inequalities and equations to solving ratios. As you might guess, we will relate two objects using the operation $\Leftrightarrow$ .

When solving an inequality, it is often necessary to multiply the inequality by a negative number and change the sign. Let us show that such an analogue for the relation operation is the operation unary minus.

We will use the sign $\bullet$ to generalize all inequalities.

Multiplying an inequality by a negative number can be broken down into two steps. Let some inequality be multiplied by a negative number . Number can always be factorized into the following: And . Both sides of the inequality can first be multiplied by a positive number . And then multiply the inequality by and change the sign to the opposite one. Since this can always be done, in what follows we will only talk about multiplying the inequality by .

Let us have some true inequality $x\bullet y$ . Let us perform the following sequence of actions with this inequality. At each step, the newly obtained inequality remains true.

Let's multiply both sides of the inequality by the sign of inequality changes to the opposite.
Let's move the right side of the inequality to the left, and the left side of the inequality to the right.
Let us again multiply both sides of the inequality by and change the sign.

Since when transferring from one part of an inequality to another, the sign of the transferred part changes to the opposite, then as a result of the actions performed, the sign changed twice. The inequality took the form: $-y\bullet -x$ . This fact means that multiplying by a negative number and changing the sign of the inequality is equivalent to multiplying by the same negative number and exchanging the left and right sides of the inequality. Wherein sign change there is no inequality.

Obviously, the ratio operation should also produce same resultif both arguments are multiplied by and they were exchanged. How does the result of a relation operation change if arguments are exchanged? The following statements are obvious.

If the result of the operation was morethen he should become less.
If the result of the operation was lessthen he should become more.
If the result of the operation was equalsthen it should remain unchanged.

Thus, if we return the arguments to their places, but leave them multiplied by then the result of the operation must be inverted.
So, it turned out verbose, but an auxiliary property that will be useful later is obtained: $-x \Leftrightarrow -y \equiv -(x \Leftrightarrow y )$ .

Problem statement and solution

Formulation of the problem. Let there be two numbers: $c_1=a_1+b_1\sqrt2$ And $c_2=a_2+b_2\sqrt2$ Where , , , – some integers. Correlate And .

Solution. Our relationship looks like: $a_1+b_1\sqrt2 \Leftrightarrow a_2+b_2\sqrt2$ .

Let's move everything to the left side and group it: $(a_1-a_2)+(b_1-b_2)\sqrt2 \Leftrightarrow 0$ .
Note that the action performed is nothing more than a subtraction. Let us introduce the following replacements: , . We substitute and get: $a+b\sqrt2 \Leftrightarrow 0$ . You can see that the relationship has simplified, so our composite number receives one more operation: subtraction. And we will correlate the difference of the first and second arguments with zero.

So our ratio is $a+b\sqrt2 \Leftrightarrow 0$ . Let's reschedule $b\sqrt2$ to the right and we get $a\Leftrightarrow -b\sqrt2$ .
Let's multiply the left side of the inequality by and the right one to $|b\sqrt2|$ . This is almost squaring, but at the same time multiplying by a non-negative number. The module can then be expanded by considering 4 cases.

So we have: $a|a| \Leftrightarrow -|b\sqrt2|b\sqrt2$ .
Let's summarize the cases in a table.

No.	Case description	Inequality
1	$a\geq 0, b\geq 0$	$a^2\Leftrightarrow -2b^2$
2	$a\geq 0, b < 0$	$a^2\Leftrightarrow 2b^2$
3	$a < 0, b\geq 0$	$-a^2 \Leftrightarrow -2b^2 \rightarrow -(a^2 \Leftrightarrow 2b^2)$
4		$-a^2\Leftrightarrow 2b^2$

After some understanding of the results obtained, we introduce a function for obtaining the sign of a number: $Sgn(v) =\{1, v>0; 0, v=0;-1,v<0\}$ and sketch out the following algorithm.

.
If or then we returnand complete the algorithm.
If then we return and complete the algorithm.
We return $s_a \times (a^2 \Leftrightarrow 2b^2)$ .

Let's describe the steps in more detail.

Sign calculation And .
Let's consider three cases.
1. If And that means And , from which it follows that the corresponding numbers are equal. Therefore we return the value .
2. If $s_a\neq 0$ And That . A number that correlates with zero: $a+0\sqrt2=a$ . If That That which means the first argument is less than the second.
3. If And $s_b\neq 0$ That . A number that correlates with zero: $0+b\sqrt2=b\sqrt2$ . If That That which means the first argument is less than the second.
At this step we already know for sure that $s_a,s_b \in \{-1;1\}$ . Condition checks whether numbers have the same signs And or not. If yes, then any (since they are the same) of these values will be the result of the ratio.
1. If And which means And which means And . That is, the number that correlates with zero is negative. The latter means that the first argument is less than the second.
At this step, we already know for sure that there are two cases left.
1. If And which means . Then you need to return $a^2\Leftrightarrow 2b^2$ . Multiplying by doesn't change anything since it's multiplying by one.
2. If And which means And . Multiplying by changes sign to the opposite.