Οδηγός Μελέτης - Εισαγωγή στον Προγραμματισμό

Α25.16 · Περικύκλωση - encirclement

Εξέταση Ιανουαρίου 2026, Θέμα 5 · Δυσκολία ★★★ · programming · Κεφάλαια: 25, 12, 22

Περικύκλωση - encirclement [25 Μονάδες]

Σε πολλά παιχνίδια στρατηγικής η περικύκλωση του αντιπάλου αφαιρεί τις δυνατότητες κίνησής του και πολύ συχνά οδηγεί σε γρήγορη νίκη. Πότε είναι όμως περικυκλωμένο ένα πιόνι του αντιπάλου; Το Σχήμα 1 δείχνει ένα παράδειγμα:

	A	B	C	D	E	F	G	H	I	J
10		O	O	O
9	O				O
8	O		X		O
7	O					O	O	O
6		O	O	O			X		O
5					O		X		O
4			O		X	O	O	O	O
3		O	X	O
2			O			O
1					O	X	O

Σχήμα 1: Τα πιόνια του μαύρου (X) στις θέσεις C3, C8, G5, G6 είναι περικυκλωμένα, ενώ στις θέσεις F1, E4 είναι ελεύθερα καθώς έχουν διέξοδο προς τα άκρα του πλέγματος.

Θεωρούμε πως ο χάρτης του παιχνιδιού είναι ένα τετραγωνικό πλέγμα και πως κάθε κελί: (1) είτε περιέχει μαύρα πιόνια (X), (2) είτε περιέχει λευκά πιόνια (O), (3) είτε είναι κενό (.). Ένα πιόνι θεωρείται περικυκλωμένο όταν δεν υπάρχει σειρά κινήσεων πάνω, κάτω, αριστερά, δεξιά (δεν επιτρέπονται διαγώνιες κινήσεις) που να επιτρέπει στο πιόνι να φτάσει στο άκρο του πλέγματος κινούμενο μόνο σε άδεια κελιά ή κελιά που περιέχουν το ίδιο χρώμα.

Γράψτε ένα πρόγραμμα το οποίο διαβάζει από την πρότυπη είσοδο (stdin) την διάσταση του πλέγματος και τα περιεχόμενα του χάρτη και τυπώνει στην πρότυπη έξοδο (stdout) για το κάθε μαύρο πιόνι αν είναι ελεύθερο ή όχι. Το πρόγραμμά σας πρέπει να είναι όσο πιο αποδοτικό γίνεται και να μπορεί να διαχειριστεί περιπτώσεις σφάλματος.

Ποια είναι η χρονική και η χωρική πολυπλοκότητα του αλγορίθμου σας; (8/25)

Παράδειγμα εκτέλεσης ακολουθεί:

$ cat map.txt
10
. . . . O X O . . .
. . O . . O . . . .
. O X O . . . . . .
. . O . X O O O O .
. . . . O . X . O .
. O O O . . X . O .
O . . . . O O O . .
O . X . O . . . . .
O . . . O . . . . .
. O O O . . . . . .
$ ./encirclement < map.txt
The following pawns are free: F1, E4
The following pawns are encircled: C3, G5, G6, C8

Υπόδειξη

Αντί να ψάχνετε ξεχωριστά έξοδο για κάθε πιόνι, αντιστρέψτε το πρόβλημα: ξεκινήστε από όλα τα διαβατά κελιά (κενά ή X) του περιγράμματος και σημαδέψτε με flood fill (DFS ή BFS, με σημάδι “επισκέφθηκα”) ό,τι φτάνετε κινούμενοι μόνο οριζόντια και κάθετα· όσα X δεν σημαδεύτηκαν είναι περικυκλωμένα. Συγκρίνετε το αρχείο με το Σχήμα 1: η πρώτη γραμμή του χάρτη στο αρχείο είναι η γραμμή 1 του σχήματος, και η έξοδος παρατάσσει τα πιόνια με αυτή τη σειρά. Ελέγξτε μη έγκυρη διάσταση, λάθος χαρακτήρες και λιγότερα κελιά από όσα περιμένετε.

Αριθμός στον οδηγό: Α25.16 (στο κεφάλαιο) · Μόνιμο αναγνωριστικό: exam-2026-jan-q5 · Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2026-jan-q5.html · Markdown (GitHub)