22ος ΠΔΠ Καμπ (seniors)
Μέγιστος διαφυγών φωτισμός (escape)

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

Στις κορυφές του πλέγματος που δεν καταλαμβάνονται από πηγές φωτός μπορούν να τοποθετηθούν επίπεδα κάτοπτρα μιας όψης, υπό γωνία \(45\) μοιρών ως προς τις πλευρές του πλέγματος. Αυτά τα κάτοπτρα αλλάζουν την πορεία του φωτός που εκπέμπεται από τις πηγές κατά \(90\) μοίρες. Μια πιθανή τοποθέτηση κατόπτρων και μια πορεία που μπορεί να ακολουθήσει το φως μέσα στο πλέγμα, αν οι πηγές στραφούν κατάλληλα, φαίνεται στο παρακάτω σχήμα.

Οι δέσμες φωτός δεν μπορούν να διέρχονται μέσα από κάτοπτρα ή από πηγές φωτός και δεν μπορούν να τέμνονται.

Πρόβλημα

Γράψτε ένα πρόγραμμα που να υπολογίζει το μεγαλύτερο πλήθος δεσμών φωτός που μπορούν να εξέρχονται από το πλέγμα.

Αρχεία Εισόδου:

Το πρόγραμμα διαβάζει τα δεδομένα από το αρχείο escape.in. Η πρώτη γραμμή του αρχείου περιέχει δύο αριθμούς, το \(N\) και το \(M\). Οι επόμενες \(M\) γραμμές περιέχουν τις συντεταγμένες \(X_i\) και \(Y_i\) μιας πηγής φωτός. Για κάθε \(1 \leq i \leq M\), ισχύει \(1 \leq X_i \leq N\) και \(1 \leq Y_i \leq N\).

Αρχεία Εξόδου:

Το αποτέλεσμα πρέπει να είναι ένα αρχείο κειμένου με όνομα escape.out. Πρέπει να περιέχει μία μόνο γραμμή με το ζητούμενο μέγιστο πλήθος δεσμών φωτός.

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

escape.in	escape.out
6 10 1 3 2 2 2 3 2 4 4 2 4 3 4 4 6 2 6 3 6 4	10

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

Περιορισμοί