EGOI-22 (2022) - Γύρος #2 - 2 (Superpiece)

View as PDF

Submit solution

All submissions

Best submissions

Points: 45 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

EGOI

Problem type

Allowed languages

C, C++, Java, Pascal, Python

Superpiece

Σας δίνεται μια σκακιέρα χωρίς τέλος. Σε αυτό το πρόβλημα η σκακιέρα είναι ένα άπειρο δισδιάστατο πλέγμα τετραγώνων, όπου κάθε τετράγωνο δεικτοδοτείται από ένα ζεύγος ακεραίων $(r, c)$ ~(r, c)~, που δηλώνουν τη γραμμή και τη στήλη αντίστοιχα. Το μόνο πιόνι που υπάρχει αυτή τη στιγμή στη σκακιέρα είναι το υπέρ-πιόνι. Σας δίνεται μια λίστα με έγκυρες κινήσεις για το υπέρ- πιόνι σας, η οποία θα καθοριστεί ως μια μη-κενή συμβολοσειρά που περιέχει ένα υποσύνολο χαρακτήρω, το " $QRBNKP$ ~QRBNKP~". Σε κάθε γύρο, το υπέρ-πιόνι μπορεί να κινείται ως ένα από τα δεδομένα πιόνια σκακιού. Το υπέρ-πιόνι είναι αρχικά τοποθετημένο στο τετράγωνο $(a, b)$ ~(a, b)~. Υπολογίστε τον ελάχιστο αριθμό κινήσεων που απαιτούνται για να φτάσετε στο τετράγωνο $(c, d)$ ~(c, d)~.

Το υποσύνολο των σκακιστικών κανόνων που ισχύουν για αυτό το πρόβλημα δίνονται παρακάτω:

Υπάρχουν έξι τύποι από πιόνια: βασίλισσα, πύργος, αξιωματικός, ίππος (αλογάκι), βασιλιάς και στρατιώτης. Αυτά, κινούνται με τον εξής τρόπο:

Η βασίλισσα (Queen) (συμβολίζεται με ' $Q$ ~Q~') μπορεί να κινηθεί σε οποιοδήποτε τετράγωνο στην ίδια γραμμή, στήλη ή διαγώνιο σε σχέση με το τετράγωνο στο οποίο βρίσκεται αυτήν τη στιγμή. Τυπικά, για οποιονδήποτε ακέραιο αριθμό $k \neq 0$ ~k \neq 0~, η βασίλισσα (queen) μπορεί να κινηθεί από το $(a, b)$ ~(a, b)~ στο $(a, b + k)$ ~(a, b + k)~, $(a + k, b)$ ~(a + k, b)~, $(a + k, b + k)$ ~(a + k, b + k)~ και $(a + k, b - k)$ ~(a + k, b - k)~.

Ο πύργος (Rook) (συμβολίζεται με ' $R$ ~R~') μπορεί να κινηθεί σε οποιοδήποτε τετράγωνο στην ίδια γραμμή ή στήλη σε σχέση με το τετράγωνο που βρίσκεται αυτή τη στιγμή. Τυπικά,για οποιονδήποτε ακέραιο αριθμό $k \neq 0$ ~k \neq 0~, ένας πύργος μπορεί να κινηθεί από το $(a, b)$ ~(a, b)~ στο $(a + k, b)$ ~(a + k, b)~ και $(a, b + k)$ ~(a, b + k)~.

Ο αξιωματικός (Bishop) (συμβολίζεται με ' $B$ ~B~') μπορεί να κινηθεί σε οποιοδήποτε τεράγωνο στην ίδια διαγώνιο σε σχέση με το τετράγωνο που βρίσκεται αυτήν τη στιγμή. Τυπικά, για οποιονδήποτε ακέραιο αριθμό $k \neq 0$ ~k \neq 0~, ένας αξιωματικός μπορεί να κινηθεί από το $(a, b)$ ~(a, b)~ στο $(a + k, b + k)$ ~(a + k, b + k)~, και $(a - k, b + k)$ ~(a - k, b + k)~.

Ο ίππος (kNight) (συμβολίζεται με ' $N$ ~N~') μπορεί να κινηθεί σε σχήμα ' $L$ ~L~': δηλαδή πρώτα κινείται δύο τετράγωνα προς συγκεκριμένη κατεύθυνση ακολουθούμενη από μια κίνηση ενός τετραγώνου σε κάθετη κατεύθυνση. Τυπικά, ο ίππος μπορεί να κινηθεί από το $(a, b)$ ~(a, b)~ στο $(a + 1, b + 2)$ ~(a + 1, b + 2)~, $(a + 1, b - 2)$ ~(a + 1, b - 2)~, $(a + 2, b + 1)$ ~(a + 2, b + 1)~, $(a + 2, b - 1)$ ~(a + 2, b - 1)~, $(a - 2, b + 1)$ ~(a - 2, b + 1)~, $(a - 2, b - 1)$ ~(a - 2, b - 1)~, $(a - 1, b + 2)$ ~(a - 1, b + 2)~ και $(a - 1, b - 2)$ ~(a - 1, b - 2)~.

Ο βασιλιάς (King) (συμβολίζεται με ' $K$ ~K~') μπορεί να κινηθεί σε οποιοδήποτε από τα οκτώ τετράγωνα που βρίσκονται ακριβώς δίπλα στο τρέχον τετράγωνο. Τυπικά, ο βασιλιάς μπορεί να κινηθεί από το $(a, b)$ ~(a, b)~ στο $(a, b + 1)$ ~(a, b + 1)~, $(a, b - 1)$ ~(a, b - 1)~, $(a + 1, b)$ ~(a + 1, b)~, $(a - 1, b)$ ~(a - 1, b)~, $(a + 1, b + 1)$ ~(a + 1, b + 1)~, $(a + 1, b - 1)$ ~(a + 1, b - 1)~, $(a - 1, b + 1)$ ~(a - 1, b + 1)~ και $(a - 1, b - 1)$ ~(a - 1, b - 1)~.

Ο στρατιώτης (Pawn) (συμβολίζεται με ' $P$ ~P~') μπορεί να μετακινηθεί ακριβώς ένα τετράγωνο επάνω. Τυπικά, ένας στρατιώτης μπορεί να κινηθεί από το $(a, b)$ ~(a, b)~ στο $(a + 1, b)$ ~(a + 1, b)~.

Σημειώστε, ότι άλλοι κανόνες ή κινήσεις που μπορεί να γνωρίζετε για το σκάκι δεν ισχύουν σε αυτό το πρόβλημα. Χρησιμοποιήστε μόνο αυτά που αναφέρονται παραπάνω.

Σημειώστε επίσης, ότι ενώ το σύμβολο που υποδηλώνει το πιόνι του σκακιού είναι σχεδόν σε όλες τις περιπτώσεις το πρώτο γράμμα της ονομασίας του (στα αγγλικά), είναι το δεύτερο γράμμα για το "kNight" (έτσι ώστε να αποφευχθεί η σύγχυση με το "King").

Είσοδος

Η πρώτη γραμμή της εισόδου περιέχει έναν ακέραιο $q$ ~q~, που αναπαριστά τον αριθμό των ερωτημάτων, στα οποία θα δοκιμαστεί το πρόγραμμά σας. Κάθε ερώτημα περιγράφεται στις δύο ακόλουθες γραμμές:

Η πρώτη γραμμή ενός ερωτήματος περιέχει μια μη-κενή συμβολοσειρά που καθορίζει το σύνολο των πιονιών του σκακιού σύμφωνα με τα οποία μπορεί να κινηθεί το υπέρ-πιόνι. Αυτή η συμβολοσειρά περιέχει ένα υποσύνολο χαρακτήρων της συμβολοσειράς σε κεφαλαία "QRBNKP", με τους χαρακτήρες που περιέχονται να εμφανίζονται με την ίδια σειρά. Με άλλα λόγια, έχει τη μορφή υπο-ακολουθίας του "QRBNKP".
Η δεύτερη γραμμή ενός ερωτήματος περιέχει τέσσερις ακέραιους αριθμούς $a, b, c, d$ ~a, b, c, d~, διαχωρισμένους με κενό διάστημα - την αρχική θέση και τη θέση στόχο του υπέρ-πιονιού. Είναι εγγυημένο ότι $(a, b) \neq (c, d)$ ~(a, b) \neq (c, d)~, δηλαδή, η αρχική θέση είναι διαφορετική από τον στόχο.

Έξοδος

Για κάθε ένα από τα $q$ ~q~ ερωτήματα, εκτυπώστε μια γραμμή που περιέχει έναν ακέραιο αριθμό $m$ ~m~ που αναπαριστά τον ελάχιστο αριθμό κινήσεων που χρειάζεται το υπέρ-πιόνι για να φτάσει στη θέση στόχο από την αρχική του θέση, γι' αυτό το ερώτημα. Εάν για κάποιο ερώτημα δεν είναι δυνατό να επιτευχθεί ο στόχος από την αρχική θέση, τότε εκτυπώστε $-1$ ~-1~ αντ' αυτού.

Περιορισμοί

$1 \le q \le 1\,000$ ~1 \le q \le 1\,000~
$-10^8 \le a, b, c, d \le 10^8$ ~-10^8 \le a, b, c, d \le 10^8~ για κάθε ερώτημα.
Η σκακιέρα είναι άπειρη προς όλες τις κατευθύνσεις.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
$1$ ~1~	$12$ ~12~	Δεν υπάρχει ο ' $N$ ~N~' χαρακτήρας και υπάρχει οπωσδήποτε ο ' $Q$ ~Q~' χαρακτήρας στην πρώτη γραμμή κάθε ερωτήματος.
$2$ ~2~	$9$ ~9~	Υπάρχουν οπωσδήποτε οι χαρακτήρες ' $Q$ ~Q~' και ' $N$ ~N~' (και οι δύο) στην πρώτη γραμμή κάθε ερωτήματος.
$3$ ~3~	$13$ ~13~	Δεν υπάρχει ο χαρακτήρας ' $Q$ ~Q~' και υπάρχει οπωσδήποτε ένας χαρακτήρας ' $R$ ~R~' στην πρώτη γραμμή κάθε ερωτήματος.
$4$ ~4~	$8$ ~8~	Η πρώτη γραμμή κάθε ερωτήματος είναι πάντα ' $B$ ~B~'.
$5$ ~5~	$6$ ~6~	Δεν υπάρχουν οι χαρακτήρες ' $Q$ ~Q~' ή ' $R$ ~R~' και υπάρχει οπωσδήποτε ένας χαρακτήρας ' $B$ ~B~' στην πρώτη γραμμή κάθε ερωτήματος.
$6$ ~6~	$31$ ~31~	Η πρώτη γραμμή κάθε ερωτήματος είναι πάντα ' $N$ ~N~'.
$7$ ~7~	$8$ ~8~	Δεν υπάρχουν οι χαρακτήρες ' $Q$ ~Q~', ' $R$ ~R~' ή ' $B$ ~B~' και υπάρχει οπωσδήποτε ένας ' $N$ ~N~' χαρακτήρας στην πρώτη γραμμή κάθε ερωτήματος.
$8$ ~8~	$7$ ~7~	Δεν υπάρχουν οι χαρακτήρες ' $Q$ ~Q~', ' $R$ ~R~', ' $B$ ~B~' ή ' $N$ ~N~' και υπάρχει οπωσδήποτε ένας ' $K$ ~K~' χαρακτήρας στην πρώτη γραμμή κάθε ερωτήματος.
$9$ ~9~	$6$ ~6~	Η πρώτη γραμμή κάθε ερωτήματος είναι πάντα ' $P$ ~P~'.

Σημειώστε ότι τα υποπροβλήματα δεν είναι ταξινομημένα με βάση τη δυσκολία τους.

Παραδείγματα

input

2
NKP
3 3 5 1
NKP
2 6 5 3

output

2
2

Επεξήγηση του 1ου παραδείγματος:

Στο πρώτο ερώτημα, σας ζητείται να πάτε από το $(3, 3)$ ~(3, 3)~ στο $(5, 1)$ ~(5, 1)~, χρησιμοποιώντας τις κινήσεις του ίππου (knight), του βασιλιά (king) και του στρατιώτη (pawn). Υπάρχουν πολλοί τρόποι για να το κάνετε αυτό με ακριβώς $2$ ~2~ κινήσεις, για παράδειγμα:

Κινηθείτε ως στρατιώτης (pawn) στο $(4, 3)$ ~(4, 3)~ και στη συνέχεια ως ίππος (knight) στο $(5, 1)$ ~(5, 1)~.
Κινηθείτε ως ίππος (knight) στο $(5, 2)$ ~(5, 2)~ και στη συνέχεια ως βασιλιάς (king) στο $(5, 1)$ ~(5, 1)~.
Κινηθείτε ως βασιλιάς (king) στο $(4, 2)$ ~(4, 2)~ και στη συνέχεια ξανά ως βασιλιάς (king) στο $(5, 1)$ ~(5, 1)~.

Δεν υπάρχει τρόπος να το πετύχετε αυτό με λιγότερες από $2$ ~2~ κινήσεις - για να το κάνετε αυτό θα χρειαζόσασταν έναν αξιωματικό (bishop) ή μια βασίλισσα (queen).

Στο δεύτερο ερώτημα σας ζητείται να πάτε από το $(2, 6)$ ~(2, 6)~ στο $(5, 3)$ ~(5, 3)~. Και πάλι, η βέλτιστη λύση είναι να χρησιμοποιήσετε δύο κινήσεις. Αυτή τη φορά, και οι δύο αυτές κινήσεις πρέπει να είναι κινήσεις ίππου (knight), με το ενδιάμεσο τετράγωνο να είναι $(4, 5)$ ~(4, 5)~ ή $(3, 4)$ ~(3, 4)~.

input

output

-1
1

Επεξήγηση του 2ου παραδείγματος:

Στο πρώτο ερώτημα σας ζητείται να πάτε από το $(2, 8)$ ~(2, 8)~ στο $(3, 6)$ ~(3, 6)~. Με προϋπόθεση μόνο τις κινήσεις του αξιωματικού (bishop), δεν είναι δυνατό να γίνει αυτό.

Στο δεύτερο ερώτημα σας ζητείται να πάτε από το $(2, 8)$ ~(2, 8)~ στο $(5, 5)$ ~(5, 5)~, και πάλι χρησιμοποιώντας μόνο τις κινήσεις του αξιωματικού (bishop). Αυτό είναι εφικτό να γίνει με $1$ ~1~ κίνηση.

input

output

2
1

Επεξήγηση του 3ου παραδείγματος:

Στο πρώτο ερώτημα σας ζητείται να πάτε από το $(3, 3)$ ~(3, 3)~ στο $(4, 5)$ ~(4, 5)~ χρησιμοποιώντας τις κινήσεις της βασίλισσας (queen). Αυτό είναι δυνατό να γίνει σε $2$ ~2~ κινήσεις, για παράδειγμα χρησιμοποιώντας το $(4, 4)$ ~(4, 4)~ ως ενδιάμεσο σημείο.

Στο δεύτερο ερώτημα σας ζητείται να πάτε από το $(4, 1)$ ~(4, 1)~ στο $(1, 4)$ ~(1, 4)~, χρησιμοποιώντας τις κινήσεις της βασίλισσας (queen) και του πύργου (rook). Αυτό είναι εφικτό να γίνει με $1$ ~1~ κίνηση.

Comments

There are no comments at the moment.