Discussion :

[SQL ninjaa]

Bonsoir, je n'arrive pas a trouver le bon chemin pour résoudre ce problème. Pourriez vous m'orienter ?

LE Problème :

4970 - A Knights' Tale
Time limit: 3.000 seconds
Imagine a chess board that extends indefinitely in both horizontal and vertical directions. N identical knights are placed on this board, each in a different square. N different squares are specially marked, which we will call the target squares, which could be different from where the knights are initially at. We would like you to determine the minimum number of knight-steps needed so that each of the target squares is occupied by one of the knights.



As illustrated in the figure, a knight moves using the normal ”L” move (1 square in one dimension and 2 squares in the other dimension.) For this problem, it is possible for more than one knight to occupy the same square while trying to reach its final destination as long as each knight ends up in a different target square.

Input

Your program will be tested on one or more test cases. Each test case is specified using 2N +1 lines.
The first line specifies (1 ≤ N ≤ 15) which is the number of knights (or targets.) The following N lines each specifies the position of a knight by specifying two integers representing the x and y location. The remaining N lines each specifies the position of a target square again by specifying two integers representing the x and y location. All coordinates are 32-bit signed integers.
The last case is followed by a line with a single zero.

Output

For each test case, print the following line:
k. m
Where k is the test case number (starting at one,) and m is the minimum number of moves.

Example

Input:
2
3 5
6 5
5 3
7 3
0
Output:
1. 3

[Obsidian]

Avant toute chose,

— As-tu besoin que l'on te traduise cet énoncé ou est-ce que tu as bien compris le problème ?
— Est-ce que c'est bien en C que tu dois écrire ton programme ?

[SQL ninjaa]

Merci pour votre réponse. J'ai très bien compris l'énoncé mais j'ai pas trouvé la bonne manière pour le résoudre, pour le langage il vaut mieux qu'il soit écrit en C ou C++ ce qui m’intéresse est l'algorithme

[kwariz]

Merci pour votre réponse. J'ai très bien compris l'énoncé mais j'ai pas trouvé la bonne manière pour le résoudre, pour le langage il vaut mieux qu'il soit écrit en C ou C++ ce qui m’intéresse est l'algorithme

Bonjour,

* si tu possèdes une fonction kd (pour knight distance) qui accepte deux paramètres S (pour les coordonnées de la case source) et T (pour les coordonnées de la case target) et qui renvoie le nombre minimum de déplacements nécessaires à un cheval pour aller de S à T
[je te rassure cette fonction existe, elle est compliquée à trouver «manuellement» mais elle se google facilement]

* si tu construis un graphe biparti complet Kn,n (où n<15 est donné par l'input) avec les «S d'un côté» et les «T de l'autre» une arête rejoignant un s de S à t de T ayant pour poids kd(s,t) (donc tous les poids sont positifs ou nuls)

* si tu as un algorithme qui détermine le couplage de poids le plus faible d'un graphe biparti

Alors le tour est joué, enfin je pense.

Remarque: le passage par un graphe biparti complet n'est pas obligatoire, c'est une façon de représenter le problème (enfin surtout de le réduire à une forme connue). Le principal est , à mon avis, de reconnaître un problème avec une distance, la question étant de minimiser une somme de distance.