22ος ΠΔΠ Γ' Φάση: Get out (getout) - Λύση
Η λυση αυτή απαιτεί γνώσεις BFS και βασικές γνώσεις bitwise τελεστών.
Επεξήγηση εκφώνησης
Μας δίνεται ένας \(N \times N\) πίνακας με κάποια \(2 \times 1\) “αυτοκίνητα” που μπορούν να μετακινηθούν οριζοντίως και κάποια \(1 \times 2\) αυτοκίνητα που μπορούν να μετακινηθούν καθέτως, όσο δεν υπάρχει κάποιο άλλο αυτοκίνητο στον δρόμο τους.
Μας ζητείται να βρούμε τον αριθμό των ελάχιστων κινήσεων ώστε η γραμμή \(R\) να μείνει ελεύθερη.
Λύση με αναζήτηση κατά βάθος
Θεωρούμε τον γράφο όπου οι κόμβοι είναι τα δυνατά states του πίνακα, δηλαδή οι πιθανές διατάξεις των αυτοκινήτων. Η ακμή \(S_1 \to S_2\) υπάρχει αν και μόνο αν στο \(S_1\) αν κουνήσουμε ένα από τα αυτοκίνητα πηγαίνουμε στο \(S_2\). Σε αυτόν τον γράφο ξεκινάμε από την αρχική διάταξη \(\textit{init}\) και στόχος μας είναι να βρούμε τον ελάχιστο αριθμό βημάτων που χρειάζεται για να πάμε σε κάποιο state όπου η γραμμή \(R\) είναι κενή.
Αφου οι ακμές δεν έχουν βάρος μπορούμε να χρησιμοποιήσουμε μία αναζήτηση κατά βάθος (BFS) ώστε να βρούμε αυτό το κοντινότερο state. Κάθε BFS λύση χρειάζεται μία αναπαράσταση για τα states, και έναν τρόπο για την εύρεση των γειτονικών κόμβων. Θα ξεκινήσουμε με μία απλή αναπαράσταση και σχετικά εκτενή κώδικα και θα προσπαθήσουμε να τον μικρύνουμε. Στο τέλος θα δείξουμε και μία εναλλακτική αναπαράσταση που χρειάζεται λιγότερη μνήμη.
Αρχική λύση
Θα ξεκινήσουμε με την αναπαράσταση όπου κρατάμε τη συντεταγμένη του δεξιότερου και υψηλότερου σημείου για κάθε αυτοκίνητο ξεχωριστά για τα οριζόντια και κάθετα αυτοκίνητα. Αυτό μας επιτρέπει να ελέχουμε αν δύο states είναι ίδια σε χρόνο γραμμικό των αυτοκινήτων στον πίνακα (τον operator< θα τον χρειαστούμε για την αποθήκευση state σε std::set).
struct State {
/* Οι συνεταγμένες των οριζόντιων και κάθετων αυτοκινήτων. */
std::vector<std::pair<char, char>> hor;
std::vector<std::pair<char, char>> ver;
bool operator<(const State& other) const {
for (int i = 0; i < hor.size(); ++i)
if (hor[i] != other.hor[i]) return hor[i] < other.hor[i];
for (int i = 0; i < ver.size(); ++i)
if (ver[i] != other.ver[i]) return ver[i] < other.ver[i];
return false;
}
};
Για να βρούμε τις πιθανές κινήσεις από ένα state, δοκιμάζουμε να μετακινήσουμε κάθε οριζόντιο ή κάθετο αυτοκίνητο σε μία από τις δύο πιθανές κατευθύνσεις. Για να ελέγχουμε γρήγορα αν μία θέση είναι άδεια, κρατάμε τον πίνακα στον \(64\)-bit ακέραιο not_free. Όπως θα παρατηρήσετε, οι παρακάτω τέσσερις περίπτωσεις έχουν πολύ παρόμοιο κώδικα.
/* Συναρτήσεις για να θέτουμε (και να βρίσκουμε) το i-οστό bit. */
void set(ull& v, char x, char y, ull t) {
char n = (x * N + y);
v = (v & ~(1ULL << n)) | (t << n);
}
bool get(ull v, char x, char y) {
return (v & (1ULL << (x * N + y))) > 0;
}
void setHor(ull& v, std::pair<char, char> pt, ull t) {
set(v, pt.first, pt.second, t);
set(v, pt.first, pt.second + 1, t);
}
void setVer(ull& v, std::pair<char, char> pt, ull t) {
set(v, pt.first, pt.second, t);
set(v, pt.first + 1, pt.second, t);
}
std::vector<State> getNext(const State& cur) {
std::vector<State> nxts;
// Κρατάμε την αναπαράσταση του πίνακα σε έναν ακέραιο με
// 64 bit (που χωράει έναν 8x8 πίνακα) για να μπορούμε να ελέγξουμε
// γρήγορα αν μία θέση είναι άδεια.
ull not_free = 0;
for (const auto& h : cur.hor) setHor(not_free, h, true);
for (const auto& v : cur.ver) setVer(not_free, v, true);
for (int j = 0; j < cur.hor.size(); ++j) {
auto h = cur.hor[j];
// Βγάζουμε προσωρινά το αυτοκίνητο από τον πίνακα.
setHor(not_free, h, false);
// Δοκιμάζουμε να μετακινήσουμε το αυτοκίνητο προς τα δεξιά.
for (int i = h.second + 1; i <= N - 2; ++i) {
if (!get(not_free, h.first, i) && !get(not_free, h.first, i+1)) {
State nxt = cur;
nxt.hor[j].second = i;
nxts.push_back(nxt);
} else break;
}
// Δοκιμάζουμε να μετακινήσουμε το αυτοκίνητο προς τα αριστερά.
for (int i = h.second - 1; i >= 0; --i) {
if (!get(not_free, h.first, i) && !get(not_free, h.first, i+1)) {
State nxt = cur;
nxt.hor[j].second = i;
nxts.push_back(nxt);
} else break;
}
// Επαναφέρουμε το αυτοκίνητο στον πίνακα.
setHor(not_free, h, true);
}
for (int j = 0; j < cur.ver.size(); ++j) {
auto v = cur.ver[j];
// Βγάζουμε προσωρινά το αυτοκίνητο από τον πίνακα.
setVer(not_free, v, false);
// Δοκιμάζουμε να μετακινήσουμε το αυτοκίνητο προς τα πάνω.
for (int i = v.first + 1; i <= N - 2; ++i) {
if (!get(not_free, i, v.second) && !get(not_free, i+1, v.second)) {
State nxt = cur;
nxt.ver[j].first = i;
nxts.push_back(nxt);
} else break;
}
// Δοκιμάζουμε να μετακινήσουμε το αυτοκίνητο προς τα κάτω.
for (int i = v.first - 1; i >= 0; --i) {
if (!get(not_free, i, v.second) && !get(not_free, i+1, v.second)) {
State nxt = cur;
nxt.ver[j].first = i;
nxts.push_back(nxt);
} else break;
}
// Επαναφέρουμε το αυτοκίνητο στον πίνακα.
setVer(not_free, v, true);
}
return nxts;
}
Ο έλεγχος για το αν ένα state έχει κενή τη \(R\)-οστή γραμμή είναι απλός:
/* Ελέγχουμε αν το δοσμένο state έχει την R-οστή γραμμή κενή. */
bool isTerminal(const State& cur) {
for (auto pr : cur.ver) {
if (pr.first == R || pr.first + 1 == R) return false;
}
for (auto pr : cur.hor) {
if (pr.first == R) return false;
}
return true;
}
Έχοντας υλοποιήσει την getNext και την isTerminal, η BFS δίνεται ως εξής:
/* Ελέγχουμε αν το δοσμένο state έχει την R-οστή γραμμή κενή. */
bool isTerminal(const State& cur) {
for (auto pr : cur.ver) {
if (pr.first == R || pr.first + 1 == R) return false;
}
for (auto pr : cur.hor) {
if (pr.first == R) return false;
}
return true;
}
Παρατηρήστε ότι κρατάμε τα states σε ένα std::set, ώστε να μην επισκεπτόμαστε κάποιο πάνω από μία φορά.
Συντομότερος κώδικας για getNext()
Για τα οριζόντια αυτοκίνητα, μπορούμε να συγχωνεύσουμε τον κώδικα για τις κινήσεις προς τα αριστερά και προς τα δεξιά. Αντίστοιχα, για τα κάθετα αυτοκίνητα, μπορούμε να συγχωνεύσουμε τις κινήσεις προς τα πάνω και κάτω.
std::vector<config> getNext(const config& cur) {
std::vector<config> nxts;
ull not_free = 0;
for (const auto& h : cur.hor) setHor(not_free, h, true);
for (const auto& v : cur.ver) setVer(not_free, v, true);
for (int j = 0; j < cur.hor.size(); ++j) {
auto h = cur.hor[j];
setHor(not_free, h, false);
// Δοκιμάζουμε να μετακινήσουμε το αυτοκίνητο αριστερά και δεξιά.
for (int dir : {-1, 1}) {
for (int i = h.second + dir; 0 <= i && i <= N - 2; i += dir) {
if (!get(not_free, h.first, i) && !get(not_free, h.first, i+1)) {
config nxt = cur;
nxt.hor[j].second = i;
nxts.push_back(nxt);
} else break;
}
}
setHor(not_free, h, true);
}
for (int j = 0; j < cur.ver.size(); ++j) {
auto v = cur.ver[j];
setVer(not_free, v, false);
// Δοκιμάζουμε να μετακινήσουμε το αυτοκίνητο πάνω και κάτω.
for (int dir : {-1, 1}) {
for (int i = v.first + dir; 0 <= i && i <= N - 2; i += dir) {
if (!get(not_free, i, v.second) && !get(not_free, i+1, v.second)) {
config nxt = cur;
nxt.ver[j].first = i;
nxts.push_back(nxt);
} else break;
}
}
setVer(not_free, v, true);
}
return nxts;
}
Ολόκληρος ο κώδικας είναι εδώ.
Ακόμη συντομότερος κώδικας για getNext()
Επίσης, μπορούμε να κρατήσουμε όλα τα αυτοκίνητα στο ίδιο vector, μαζί με έναν bool που μας λέει αν είναι οριζόντιο ή κάθετο. Με αυτόν τον τρόπο, ορίζοντας κάποιες βοηθητικές συναρτήσεις, μπορούμε να συγχωνεύσουμε τις τέσσερις κινήσεις:
char get_diff_coord(std::tuple<char, char, bool> pt) {
return isHorizontal(pt) ? std::get<1>(pt) : std::get<0>(pt);
}
std::pair<char, char> get_same_coord(std::tuple<char, char, bool> pt, char y) {
return isHorizontal(pt) ? std::make_pair(std::get<0>(pt), y) : std::make_pair(y, std::get<1>(pt));
}
std::vector<State> getNext(const State& cur) {
std::vector<State> nxts;
ull not_free = 0;
for (const auto& pt : cur.pts) set(not_free, pt, true);
for (int j = 0; j < cur.pts.size(); ++j) {
auto pt = cur.pts[j];
set(not_free, pt, false);
for (int dir : {-1, 1}) {
for (int i = get_diff_coord(pt) + dir; 0 <= i && i <= N - 2; i += dir) {
if (!get(not_free, get_same_coord(pt, i)) && !get(not_free, get_same_coord(pt, i+1))) {
State nxt = cur;
if (isHorizontal(pt)) std::get<1>(nxt.pts[j]) = i;
else std::get<0>(nxt.pts[j]) = i;
nxts.push_back(nxt);
} else break;
}
}
set(not_free, pt, true);
}
return nxts;
}
Ολόκληρος ο κώδικας είναι εδώ.
Αναπαράσταση με λιγότερη μνήμη
Αντί για το vector από συντεταγμένες, μπορούμε να κρατήσουμε έναν binary πίνακα με τις θέσεις που ξεκινάνε οριζόντια αυτοκίνητα και έναν πίνακα με τις θέσεις που ξεκινάνε κάθετα αυτοκίνητα. Αφού το μέγεθος του κάθε πίνακα είναι το πολύ \(8\times 8\), μπορούμε να τον αποθηκεύσουμε σε έναν \(64\)-bit ακέραιο. Με αυτόν τον τρόπο χρειαζόμαστε λιγότερη μνήμη στην χειρότερη περίπτωση και ο έλεγχος για ισότητα μεταξύ states γίνεται πιο γρήγορος (απλή σύγκριση ακεραίων).
struct State {
ull mask[2];
State() { mask[0] = mask[1] = 0; }
bool operator<(const State& other) const {
if (mask[0] != other.mask[0]) return mask[0] < other.mask[0];
return mask[1] < other.mask[1];
}
};
Από την άλλη η εύρεση των γειτονικών states είναι πιο αργή αφού πρέπει να διατρέξουμε όλες τις θέσεις του πίνακα για να βρούμε ποιες θέσεις είναι κατειλημμένες.
std::vector<State> getNext(const State& cur) {
std::vector<State> nxts;
ull not_free = 0;
for (bool is_vertical : {0, 1})
for (char x = 0; x < N; ++x)
for (char y = 0; y < N; ++y) {
if (!get(cur.mask[is_vertical], {x, y})) continue;
std::tuple<char, char, bool> pt({ x, y, !is_vertical });
set(not_free, pt, true);
}
for (bool is_vertical : {0, 1})
for (char x = 0; x < N; ++x)
for (char y = 0; y < N; ++y) {
if (!get(cur.mask[is_vertical], {x, y})) continue;
std::tuple<char, char, bool> pt({ x, y, !is_vertical });
set(not_free, pt, false);
for (int dir : {-1, 1}) {
for (int i = get_diff_coord(pt) + dir; 0 <= i && i <= N - 2; i += dir) {
if (!get(not_free, get_same_coord(pt, i)) && !get(not_free, get_same_coord(pt, i+1))) {
State nxt = cur;
set(nxt.mask[is_vertical], x, y, false);
set(nxt.mask[is_vertical], is_vertical ? i : x, is_vertical ? y : i, true);
nxts.push_back(nxt);
} else break;
}
}
set(not_free, pt, true);
}
return nxts;
}
Ολόκληρος ο κώδικας είναι εδώ.