$\begingroup$

I have a 10x10 grid of squares, where each square represents a sequential number from 0 to 99.

9 | 19 | 29 | 39 | 49 | 59 | 69 | 79 | 89 | 99 |
8 | 18 | 28 | 38 | 48 | 58 | 68 | 78 | 88 | 98 |
7 | 17 | 27 | 37 | 47 | 57 | 67 | 77 | 87 | 97 |
6 | 16 | 26 | 36 | 46 | 56 | 66 | 76 | 86 | 96 |
5 | 15 | 25 | 35 | 45 | 55 | 65 | 75 | 85 | 95 |
4 | 14 | 24 | 34 | 44 | 54 | 64 | 74 | 84 | 94 |
3 | 13 | 23 | 33 | 43 | 53 | 63 | 73 | 83 | 93 |
2 | 12 | 22 | 32 | 42 | 52 | 62 | 72 | 82 | 92 |
1 | 11 | 21 | 31 | 41 | 51 | 61 | 71 | 81 | 91 |
0 | 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 |

How to calculate the distance between square to another square. The distance is calculated by steps like king in chess, it can move only 1 step adjacently / diagonally.

For example:

• the distance between 0 to 63 is 6 (11, 22, 33, 43, 53, 63)
• the distance between 32 and 39 is 7 (33, 34, 35, 36, 37, 38, 39)
• the distance between 33 and 33 is 0
• the distance between 18 and 60 is 8 (27, 36, 45, 54, 63, 62, 61, 60)

If possible, it should work on 8x8 grid as well or 3x8 and so on..

Thank you so much in advance

$\endgroup$ 3

2 Answers

$\begingroup$

To make the notation easier, I'm going to use $(r,c)$ to represent a cell where $r$ is the row number and $c$ is the column number.

Consider two cells, $(r_1, c_1)$ and $(r_2, c_2)$. Define their distance as,

$$d((r_1, c_1),(r_2,c_2)) = \max\{|r_2-r_1|,|c_2-c_1|\}.$$

So in the context of the grid with the numbers, you simply need to look at the difference between the one's digits and the difference between the ten's digits and take the larger of the two.

$\endgroup$ 7 $\begingroup$

I get two nodes have distance $1$ if they share either a side or a corner, and the distance between any two squares is the length of the shortest path between them.

It is evident that the shortest path $(a,b)\to (c,d)$ has the same length as the shortest paths $(c,b)\to(a,d)$, or $(a,d)\to(c,b)$: you are just choosing a different diagonal on the rectangle $\langle(a,b);(c,b); (c,d);(a,d)\rangle$.

It is also evident that the shortest path $(a,b)\to(c,d)$ is as long as the shortest path $(c,d)\to(a,b)$.

So, up to the aforementioned symmetries, you can always reduce to the case $(a,b)\to(c,d)$, with $a\le c$ and $b\le d$.

Every time you move to the right, you have the option of getting a free move up by moving through the corner instead of the side; viceversa, every time you move up you can move left for free. So, the length of the path $(a,b)\to (c,d)$ is at most $\max\{\lvert b-a\rvert,\lvert c-d\rvert\}$.

On the other hand, you need at least to move as much in one of the co-ordinate directions to get from $(a,b)$ to $(c,d)$.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy