Switch the Lamp On
Baltic Olympiad in Informatics: 2011 Day 1, Problem 3
Ο Casper σχεδιάζει ένα ηλεκτρονικό κύκλωμα σε μια ορθογώνια πλάκα πλέγματος . Υπάρχουν τετράγωνα πλακίδια που είναι ευθυγραμμισμένα στο πλέγμα της πλάκας. Δύο (από τις τέσσερις) απέναντι γωνίες κάθε πλακιδίου συνδέονται με ένα καλώδιο.
Μια πηγή ρεύματος είναι συνδεδεμένη στην επάνω αριστερή γωνία της πλάκας. Μια λάμπα συνδέεται στην κάτω δεξιά γωνία της πλάκας. Η λάμπα είναι αναμμένη μόνο εάν υπάρχει μια διαδρομή καλωδίων που να συνδέει την πηγή ρεύματος με τη λάμπα. Για να μπορέσει να ανάψει η λάμπα, μπορεί να περιστραφεί οποιοσδήποτε αριθμός πλακιδίων κατά μοίρες (και προς τις δύο κατευθύνσεις).
Στην παραπάνω εικόνα η λάμπα είναι σβηστή. Εάν οποιοδήποτε από τα πλακίδια της δεύτερης στήλης από δεξιά περιστραφεί κατά μοίρες, η πηγή ρεύματος και η λάμπα θα συνδεθούν και η λάμπα τότε θα ανάψει.
Γράψτε ένα πρόγραμμα, που να βρίσκει τον ελάχιστο αριθμό πλακιδίων που πρέπει να περιστραφούν κατά μοίρες ώστε να ανάψει η λάμπα.
Περιορισμοί
Υποερώτημα
Υποερώτημα
Κανένας επιπλέον περιορισμός
Είσοδος
Η πρώτη γραμμή της εισόδου θα περιέχει δύο ακέραιους αριθμούς και , τις διαστάσεις της πλάκας.
Σε κάθε μία από τις επόμενες γραμμές, θα υπάρχουν χαρακτήρες - είτε \
είτε /
- οι οποίοι υποδεικνύουν την κατεύθυνση του καλωδίου που συνδέει τις απέναντι κορυφές του αντίστοιχου πλακιδίου.
Έξοδος
Πρέπει να υπάρχει ακριβώς μία γραμμή εξόδου. Εάν είναι δυνατόν να ανάψει η λάμπα, η γραμμή αυτή πρέπει να περιέχει μόνο έναν ακέραιο αριθμό: τον ελάχιστο αριθμό πλακιδίων που πρέπει να στραφούν για να ανάψει η λάμπα. Εάν αυτό δεν είναι δυνατό, εξάγετε τη συμβολοσειρά: .
Παράδειγμα
input
3 5
\\/\\
\\///
/\\\\
output
1
Επεξήγηση παραδείγματος:
Το παράδειγμα αυτό αντιστοιχεί στην εικόνα της εκφώνησης.
Comments