Manhattan – Épreuve régionale 2012

Niveau 1

Énoncé

Pour cet exercice, nous considérerons la distance de Manhattan : déplacement vertical plus déplacement horizontal. Par exemple, la distance entre (2, 5) et (4, 2) est de 2 + 3 = 5.

Joseph Marchand a beaucoup d'amis et aimerait aller voir le plus proche de chez lui (le plus proche au sens de la distance de Manhattan). Calculez la distance entre Joseph et son ami le plus proche.

Entrée

L'entrée comprendra :

  • Sur la première ligne, un entier H représentant la hauteur de la carte.
  • Sur la seconde ligne, un entier L représentant la largeur de la carte.
  • Sur la troisième ligne, une paire d'entiers (Jx, Jy) représentant la position de Joseph.
  • Sur la quatrième ligne, un entier K représentant le nombre d'amis de Joseph.
  • Sur les K lignes suivantes, la position des amis de Joseph sur la carte.

Sortie

La distance de Manhattan entre Joseph et son plus proche ami.

Contraintes

  • 1 <= H <= 200
  • 1 <= L <= 200
  • 0 <= Jx < H
  • 0 <= Jy < L
  • 1 <= K <= 200
  • 0 <= Px < H
  • 0 <= Py < L

Contraintes d'exécution

Utilisation mémoire maximum
600 kilo-octets
Temps d'exécution maximum
200 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
5 5
0 0
1
4 4
Exemple de sortie
8
Exemple d'entrée
3 3
1 1
1
0 0
Exemple de sortie
2
Exemple d'entrée
10 10
5 3
5
0 3
2 3
6 6
8 0
5 9
Exemple de sortie
3