Αρχική > 24ος ΠΔΠ

24ος ΠΔΠ Καμπ (juniors)
Βιαστικός ίππος (knight)

Δίνεται μία σκακιέρα διαστάσεων \(N \times M\), στην κάτω αριστερή γωνία της οποίας βρίσκεται ένας ίππος. Ο ίππος στο σκάκι κινείται κάνοντας ένα «Γ», δηλαδή δύο θέσεις προς τη μία κατεύθυνση (οριζόντια ή κάθετα) και μία θέση προς την άλλη κατεύθυνση. Ζητείται το ελάχιστο πλήθος κινήσεων που πρέπει να κάνει ο ίππος για να βρεθεί στην πάνω δεξιά γωνία της σκακιέρας.

Αρχεία Εισόδου (knight.in):

Η πρώτη γραμμή της εισόδου θα περιέχει δύο ακέραιους αριθμούς \(N\) και \(M\), χωρισμένους με ένα κενό διάστημα: τις διαστάσεις της σκακιέρας.

Αρχεία Εξόδου (knight.out):

Η έξοδος πρέπει να αποτελείται από μία γραμμή που να περιέχει ακριβώς έναν ακέραιο αριθμό: το ελάχιστο πλήθος κινήσεων που φέρνουν τον ίππο από την κάτω αριστερή στην πάνω δεξιά γωνία της σκακιέρας.

Παραδείγματα Αρχείων Εισόδου - Εξόδου:

1o

knight.in knight.out
5 6 3
Οι τρεις κινήσεις του αλόγου για το 1ο παράδειγμα: (1,1)->(3,2)->(5,3)->(6,5)

2o

knight.in knight.out
8 8 6
Οι έξι κινήσεις του αλόγου για το 2ο παράδειγμα: (1,1)->(2,3)->(3,5)->(4,7)->(5,5)->(6,7)->(8,8)

Περιορισμοί:

  • \(5 \leq N, M \leq 1.000\).
  • Όριο χρόνου εκτέλεσης: \(1\) sec.
  • Όριο μνήμης: \(128\) MB.