Comment calculer la distance entre 2 points dans une matrice 2D

Question

Je suis à la fois nouveau sur ce site web et nouveau en C. J'ai besoin d'un programme pour trouver les "sauts" moyens nécessaires à partir de tous les points.

L'idée est la suivante : Trouver la distance de "saut" de 1 à 2, 1 à 3, 1 à 4 ... 1 à 9, ou trouver 2 à 1, 2 à 3, 2 à 4 2 à 5 etc.

Les faire sur la première ligne est simple, il suffit de (2-1) ou (3-1) et vous obtenez le bon numéro. Mais si je veux trouver la distance entre 1 et 4 ou 1 et 8, je n'en ai absolument aucune idée. Les dimensions de la matrice devraient potentiellement être modifiables. Mais je veux juste de l'aide pour une matrice 3x3.

Quelqu'un pourrait-il me montrer comment le trouver ?

Le saut est un déplacement vertical ou horizontal d'un point à un autre. De 1 à 2 = 1, de 1 à 9 = 4 (uniquement pour le chemin le plus court).

Answer 1

La définition de la "distance" dans ce type de problèmes est toujours délicate.

Imaginez que les points sont des marques sur un terrain, et que vous pouvez vous promener librement dessus. Vous pourriez alors emprunter n'importe quel chemin d'un point à l'autre. Le chemin le plus court serait alors une ligne droite ; sa longueur serait celle du vecteur qui relie les points, qui se trouve être le vecteur de différence entre les positions de deux points. Cette longueur peut être calculée à l'aide du théorème de Pythagore : dist = sqrt((x2-x1)^2 + (y2-y1)^2) . On appelle cela la distance euclidienne entre les points.

Imaginez maintenant que vous êtes dans une ville, et que chaque point est un bâtiment. Vous ne pouvez pas marcher sur un bâtiment, donc les seules options sont d'aller soit vers le haut/bas, soit vers la gauche/droite. Dans ce cas, la distance la plus courte est donnée par la somme des composantes du vecteur de différence, ce qui est la façon mathématique de dire que "descendre de 2 pâtés de maisons puis aller à gauche d'un pâté de maisons" signifie marcher sur une distance de 3 pâtés de maisons : dist = abs(x2-x1) + abs(y2-y1) . C'est ce qu'on appelle la distance de Manhattan entre les points.

Dans votre problème, cependant, il semble que le seul mouvement possible soit de sauter à un point adjacent, en une seule étape, diagonales autorisées. Le problème devient alors un peu plus délicat, car le chemin est très irrégulier. Vous avez besoin d'un peu de théorie des graphes ici, très utile pour modéliser des problèmes avec des éléments liés, ou "nœuds". Chaque point serait un nœud, connecté à ses voisins, et le problème serait de trouver le chemin le plus court vers un autre point donné. Si les sauts ont des poids différents (par exemple, si les sauts en diagonale sont plus difficiles), un moyen facile de résoudre ce problème serait l'algorithme de Dijkstra ; plus de détails sur la mise en œuvre à l'adresse suivante Wikipedia .

Si le coût est toujours le même, alors le problème se réduit à compter le nombre de sauts dans une recherche en largeur (Breadth-First Search) du point de destination depuis la source.

Answer 2

Définissons la distance de "saut" : "le nombre de sauts nécessaires pour atteindre le point A [A _x ,A _y ] au point B [B _x ,B _y ]."

Il peut y avoir deux façons d'autoriser les sauts :

1. Horizontalement/Verticalement
   Dans ce cas, vous pouvez aller vers le haut/bas ou vers la gauche/droite. Comme vous devez déplacer l'axe X et l'axe Y indépendamment, vos réponses sont les suivantes :
   jumpDistance = abs(Bx - Ax) + abs(By - Ay);

2. Horizontalement/Verticalement et aussi Diagonalement
   Dans ce cas, vous pouvez aller vers le haut/bas ou la gauche/droite et aussi en diagonale. Quelle est la différence avec Case 1 c'est que vous avez maintenant la possibilité de changer votre axe X et votre axe Y ensemble au prix d'un seul saut. Votre réponse est maintenant :
   jumpDistance = Max(abs(Bx - Ax),abs(By - Ay));

Answer 3

Quelle est la définition de "distance de saut" ?

Si vous voulez savoir combien de sauts il faut à un homme pour aller de la case M à la case N, s'il ne peut sauter que verticalement et horizontalement, il y a une possibilité :

dist = abs(x2 - x1) + abs(y2 - y1);

Par exemple la distance de saut entre 1 et 9 est : |3-1|+|3-1| = 4

Answer 4

Il existe deux façons de calculer la distance de saut. 1) lorsque seuls les mouvements horizontaux et verticaux sont autorisés, dans ce cas, tout ce que vous devez faire est de former un rectangle entre les deux points et de calculer la longueur de deux côtés adjacents. Par exemple, si vous voulez vous déplacer de 1 à 9, vous devez d'abord vous déplacer de 1 à 3, puis de 3 à 9 (convertissez-le en code). 2) lorsque les mouvements dans les huit directions sont autorisés, les choses se compliquent. Par exemple, si vous voulez vous déplacer de 1 à 6, supposez. Ce que vous devrez faire est de vous déplacer de 1 à 5. Et ensuite de 5 à 6. La façon de le faire en code est de trouver le maximum entre la différence dans les coordonnées x et y. Dans cet exemple, en coordonnées x, la différence est de 2 (3-1) et en coordonnées y, la différence est de 1 (2-1). Le maximum de cette différence est donc 2. Voici donc la réponse. (Convertir en code)