33ος ΠΔΠ B' Φάση: Ο Δίκαιος Λαβύρινθος (fairmaze) - Λύση

Συγγραφέας: Κωνσταντίνος Μποκής

Επεξήγηση εκφώνησης

Μας δίνεται ένας κατευθυνόμενος γράφος με \(N\times M\) κόμβους. Κάθε κόμβος έχει ακριβώς μια ακμή εξόδου, άρα έχουμε \(N\times M\) κατευθυνόμενες ακμές. Οι ακραίοι κόμβοι ενδέχεται να έχουν διέξοδο εκτός του γράφου. Μας ζητείται να υπολογίσουμε πόσοι κόμβοι του γράφου δεν έχουν άμεση ή έμμεση (μέσω άλλων κόμβων) διέξοδο εκτός του γράφου.

Μια λύση είναι να βρούμε όλους τους ακραίους κόμβους που έχουν ακμή διέξοδο και για κάθε έναν από αυτούς να ακολουθήσουμε τις διαδρομές που οδηγούν σε αυτούς. Η λύση αυτή μπορεί να υλοποιηθεί με αναζήτηση κατά βάθος (DFS). Άλλη λύση είναι να κάνουμε αναζήτηση κατά βάθος (DFS) από κάθε κόμβο που συναντάμε. Μια ακόμα λύση, είναι να επεξεργαστούμε κάθε κόμβο με τη σειρά και να τον εντάξουμε σε μια ομάδα με τους κόμβους που συναντά στη διαδρομή του. Αν στο τέλος της διαδρομής έχουμε διέξοδο, τότε όλοι οι κόμβοι της ομάδας αυτής έχουν διέξοδο και δεν προσμετρώνται στην απάντηση μας. Η λύση αυτή υλοποιείται με τη δομή δεδομένων union-find.

Εξερεύνηση ακραίων κόμβων και αναζήτηση κατά βάθος αναδρομικά

Ξεκινάμε από κάθε έναν από τους \(2\cdot N + 2\cdot M\) ακραίους κόμβους. Προσέξτε ότι κάθε ένας από τους \(4\) γωνιακούς κόμβους, έχει \(2\) δυνατές διεξόδους, οπότε αυτούς τους \(4\) κόμβους τους ελέγχουμε και με τις δύο δυνατές διεξόδους. Εφόσον ξεκινούμε ανάποδα (από την έξοδο του γράφου), θα κινούμαστε και ανάποδα (προς τις ακμές εισόδου, δηλαδή με ‘D’ προς τα πάνω, με ‘L’ προς τα δεξιά κλπ). Κάθε κόμβο που μπορέσαμε να εντάξουμε στην ομάδα μας τον μαρκάρουμε ώστε να μην ασχοληθούμε πάλι μαζί του. Ο αλγόριθμος μας έχει πολυπλοκότητα \(\mathcal{O}(N \cdot M)\) και χρειάζεται μνήμη \(\mathcal{O}(N \cdot M)\).

Υπάρχουν δύο κλασικοί τρόποι υλοποίησης της DFS: αναδρομικά ή γραμμικά. Ο αναδρομικός τρόπος ακολουθεί:

#include <cstdio>

const int RMAX = 1000, CMAX = 1000;
int R,C;//R=rows(γραμμές), C=columns(στήλες)
char G[RMAX][CMAX+1];//το +1 για την αποθήκευση του τελικού '\0' στο string
bool visit[RMAX][CMAX];

long dfs(int y,int x,char exit){
    //ο κόμβος στη γραμμή y και στήλη x αν έχει τιμή exit, έχει πρόσβαση σε έξοδο
    //θα επιστρέψουμε πόσους κόμβους βρήκαμε στην ομάδα, που έχουν έξοδο
    if(y<0||x<0 || x>=C||y>=R || visit[y][x] || G[y][x]!=exit)
        return 0;
    visit[y][x] = true;
    return 1L+dfs(y-1,x,'D') + dfs(y+1,x,'U') + dfs(y,x-1,'R') + dfs(y,x+1,'L');
}

int main(){
    freopen("fairmaze.in","r",stdin);
    freopen("fairmaze.out","w",stdout);
    scanf("%d%d",&R,&C);
        
    for(int y=0;y<R;y++)
        scanf(" %s",G[y]);
    
    long ans = R * C;
    for(int y=0;y<R;y++)
        ans -= dfs(y,0,'L') + dfs(y,C-1,'R');
    for(int x=0;x<C;x++)
        ans -= dfs(0,x,'U') + dfs(R-1,x,'D');

    printf("%ld\n",ans);
    return 0;
}

Παρατηρήστε ότι αν κάποιο test case έχει σχεδιαστεί σαν ένα μονοπάτι που να περνά διαδοχικά από όλους του κόμβους, τότε θα έχουμε \(1.000.000\) αναδρομικές κλήσεις της DFS, με ενδεχόμενη υπερχείλιση (overflow) της μνήμης σωρού κλήσεων (call stack) και πρόκληση σφάλματος κατάτμησης. Για να αποφύγουμε το πρόβλημα αυτό, χρησιμοποιούμε μία δομή επανάληψης και μία stack (χωρίς αναδρομικές κλήσεις) δηλαδή υλοποιούμε τη γραμμική DFS:

struct test {
    int x,y;
    char escape_path;
    test(int y,int x,char escape_path):x(x),y(y),escape_path(escape_path){}
};

long dfs(int y,int x,char escape_path){
    //ο κόμβος στη γραμμή y και στήλη x αν έχει τιμή escape_path, έχει διέξοδο
    //θα επιστρέψουμε πόσους κόμβους βρήκαμε στην ομάδα, που έχουν διέξοδο
    long count = 0;
    stack<test> S;
    S.push(test(y,x,escape_path));
    
    while(!S.empty()){
        y = S.top().y, x = S.top().x, escape_path = S.top().escape_path;
        S.pop();
        if(y<0||x<0 || x>=C||y>=R || visit[y][x] || G[y][x]!=escape_path)
            continue;

        visit[y][x] = true;
        count++;
        S.push(test(y-1,x,'D'));
        S.push(test(y+1,x,'U'));
        S.push(test(y,x-1,'R'));
        S.push(test(y,x+1,'L'));
    }
    return count;
}

Η λύση αυτή περνά όλα τα test cases.

Εξερεύνηση κατά βάθος αναδρομικά

Κάνουμε ένα loop για κάθε κόμβο και με αναζήτηση κατά βάθος (DFS) ελέγχουμε αν βγαίνουμε εκτός λαβυρίνθου. Σημειώνουμε σε κάθε κόμβο ότι περάσαμε στον πίνακα \(\mathit{visit}\) και αν έχει διέξοδο στον πίνακα \(\mathit{escapes}\) και φροντίζουμε να μην ξαναπεράσουμε από εκεί. Καταμετρούμε τους κόμβους που δεν έχουν διέξοδο. Ο αλγόριθμος μας έχει πολυπλοκότητα \(\mathcal{O}(N \cdot M)\) και χρειάζεται μνήμη \(\mathcal{O}(N \cdot M)\).

bool dfs(int y,int x){//true if escapes
    if(y<0||x<0 || x>=C||y>=R)
        return true;
    if(visit[y][x])//έχουμε υπολογίσει τη διαδρομή από εδώ και μετά
        return escapes[y][x];//άρα ξέρουμε αν βγαίνουμε εκτός
        
    visit[y][x] = true;//αν η dfs βρεί κάποιον ατέρμονο κύκλο
    bool result = false;//θα επιστρέψει false
    switch(G[y][x]){
        case 'U':result = dfs(y-1,x);break;
        case 'D':result = dfs(y+1,x);break;
        case 'L':result = dfs(y,x-1);break;
        case 'R':result = dfs(y,x+1);break;
    }
    return escapes[y][x] = result;
}

Η λύση αυτή ενδέχεται να προκαλέσει υπερχείλιση (overflow) της μνήμης σωρού κλήσεων (call stack) και πρόκληση σφάλματος κατάτμησης σε ειδικά σχεδιασμένα test cases.

Παρατηρήστε ότι κάθε κόμβος έχει μόνο μια έξοδο, άρα δεν υπάρχουν διακλαδώσεις και η αναζήτηση μπορεί να γίνει με έναν απλό βρόγχο για να ακολουθήσουμε το μονοπάτι. Όταν βρούμε το τέλος του μονοπατιού ή καταλήξουμε σε κόμβο που έχουμε ξαναεπισκευτεί, ενημερώνουμε όλους τους κόμβους που προσπεράσαμε. Ο αλγόριθμος μας εξερευνεί κάθε κόμβο μια φορά και ενημερώνει μέσω του πίνακα \(\mathit{path}\) κάθε κόμβο, μια φορά, άρα έχει πολυπλοκότητα \(\mathcal{O}(N \cdot M)\) και χρειάζεται μνήμη \(\mathcal{O}(N\cdot M)\).

struct step {
    int y,x;
    step(int y,int x):y(y),x(x){}
    step(){}
} path[RMAX*CMAX];
int path_count;

bool dfs(int y,int x){
    if(visit[y][x])//έχουμε εξερευνήσει τον κόμβο
        return escapes[y][x];
    
    bool result = false;
    path_count = 0;
    
    while(true){
        //αποθήκευσε τη διαδρομή που εξερευνούμε στο path[]
        //ώστε στο "γυρισμό" να αποθηκεύσουμε το αποτέλεσμα
        path[path_count++] = step(y,x);
        
        visit[y][x] = true;
        switch(G[y][x]){
            case 'U':y--;break;
            case 'D':y++;break;
            case 'L':x--;break;
            case 'R':x++;break;
        }
        if(y<0||x<0 || x>=C||y>=R){
            result = true;//βρήκαμε διέξοδο
            break;
        }
        if(visit[y][x]){//τον έχουμε εξερευνήσει
            result = escapes[y][x];
            break;
        }
    }
    
    if(result)
        for(int i=0;i<path_count;i++)
            escapes[path[i].y][path[i].x] = result;
        
    return result;
}

Η λύση αυτή περνά όλα τα test cases.

Συνένωση κόμβων με χρήση της δομής union-find

Γνώσεις που θα χρειαστούμε: union-find disjoint-sets

Θα εξερευνήσουμε με τη σειρά έναν έναν όλους τους κόμβους, από αριστερά προς τα δεξιά και από πάνω προς τα κάτω. Θα ενώσουμε κάθε κόμβο με την ομάδα του κόμβου που βρίσκεται στη γραμμή εξόδου του. Αν ένας κόμβος έχει διέξοδο, τότε μαρκάρουμε όλη την ομάδα ότι έχει διέξοδο (συνάρτηση dj_escapes()). Χρειάζεται να διατρέξουμε μία φορά τον πίνακα, άρα χρειάζονται \(\mathcal{O}(N\cdot M)\) βήματα. Η μνήμη που χρειάζεται είναι επίσης \(\mathcal{O}(N \cdot M)\).

Η αναζήτηση εκπροσώπου και η συνένωση ομάδων, γίνεται amortized σχεδόν σε σταθερό χρόνο¹ και δεν αλλάζει την ασυμπτωτική πολυπλοκότητα της λύσης.

Στο τέλος αθροίζουμε στην \(\mathit{ans}\) τα πλήθη από τις διαφορετικές ομάδες που έχουν δημιουργηθεί στη union-find και δεν έχουν διέξοδο. Το τελευταίο αυτό στάδιο θέλει άλλα \(\mathcal{O}(N\cdot M)\) βήματα για την καταμέτρηση.

#include <cstdio>
#include <cstring>
#include <algorithm>

const int RMAX = 1000, CMAX = 1000;
int R,C;//R=rows(γραμμές), C=columns(στήλες)
char G[RMAX][CMAX+1];//το +1 για την αποθήκευση του τελικού '\0' στο string

struct dj_team {
    long head;//εκπρόσωπος ομάδας
    long count;//πλήθος ομάδας
    bool escapes;//αν η ομάδα έχει διέξοδο
} dj[RMAX * CMAX];
long ans;

inline long yx(int y,int x){//μετέτρεψε την 2D συντεταγμένη σε 1D
    return long(y)*C + x;
}

long dj_find(long yx){
    if(dj[yx].head==yx)
        return yx;
    return dj[yx].head = dj_find(dj[yx].head);
}

void dj_escapes(int yx){//μάρκαρε την ομάδα του yx ότι έχει διέξοδο
    dj[dj_find(yx)].escapes = true;
}

bool dj_union(long yx1,long yx2){
    yx1 = dj_find(yx1), yx2 = dj_find(yx2);
    if(yx1!=yx2){
        if(dj[yx1].count<dj[yx2].count)
            std::swap(yx1,yx2);
        dj[yx1].count += dj[yx2].count;
        dj[yx1].escapes |= dj[yx2].escapes;
        dj[yx2].head = yx1;
        return true;
    }
    return false;
}
    
int main(){
    freopen("fairmaze.in","r",stdin);
    freopen("fairmaze.out","w",stdout);

    scanf("%d%d",&R,&C);
    for(long i=0,n=R*C;i<n;i++){
        dj[i].head  = i;
        dj[i].count = 1;
    }    
    for(int y=0;y<R;y++){
        scanf(" %s",G[y]);
        for(int x=0;x<C;x++){
            long yx1 = dj_find(yx(y,x));
            
            switch(G[y][x]){
                case 'U':
                    if(y==0) dj_escapes(yx1);
                    else dj_union(yx1,yx(y-1,x));
                    break;
                case 'D':
                    if(y==R-1) dj_escapes(yx1);
                    else dj_union(yx1,yx(y+1,x));
                    break;
                case 'L':
                    if(x==0) dj_escapes(yx1);
                    else dj_union(yx1,yx(y,x-1));
                    break;
                case 'R':
                    if(x==C-1) dj_escapes(yx1);
                    else dj_union(yx1,yx(y,x+1));
                    break;
            }
        }
    }
    
    //άθροισε τα πλήθη των ομάδων που δεν βγαίνουν
    long ans = 0;
    for(long i=0,n=R*C;i<n;i++)
        if(dj[i].head==i && !dj[i].escapes)
            ans += dj[i].count;

    printf("%ld\n",ans);
    return 0;
}

Μπορούμε να εξαλείψουμε το τελευταίο στάδιο της καταμέτρησης αν φροντίσουμε να διατηρούμε συνεχώς ενημερωμένη τη μεταβλητή \(\mathit{ans}\). Για το σκοπό αυτό θέτουμε ως αρχική τιμή στην \(\mathit{ans}\) το πλήθος όλων των κόμβων. Καθώς ανακαλύπτουμε ομάδες με διέξοδο, αφαιρούμε το πλήθος των κόμβων τους από την \(\mathit{ans}\).

bool dj_union(long yx1,long yx2){
    yx1 = dj_find(yx1), yx2 = dj_find(yx2);
    if(yx1!=yx2){
        if(dj[yx1].count<dj[yx2].count)
            std::swap(yx1,yx2);
        //αφαίρεσε τις ομάδες από το ans πριν την ένωση αν χρειάζεται
        if(!dj[yx1].escapes) ans-=dj[yx1].count;
        if(!dj[yx2].escapes) ans-=dj[yx2].count;
        //συνένωσε τις ομάδες
        dj[yx1].count   += dj[yx2].count;
        dj[yx1].escapes |= dj[yx2].escapes;
        dj[yx2].head    =  yx1;
        //ενημέρωσε το ans με την ενωμένη ομάδα αν χρειάζεται
        if(!dj[yx1].escapes) ans+=dj[yx1].count;
        return true;
    }
    return false;
}

και μιά μικρή παραλλαγή με μετατροπή του switch σε βρόγχο με χρήση πίνακα:

    struct checks {
        char edge;//τιμή ακμής εξόδου για διέξοδο
        int dy,dx;
    } Z[] = {
        {'U',-1, 0},
        {'D', 1, 0},
        {'L', 0,-1},
        {'R', 0, 1},
    };
    
    for(int y=0;y<R;y++){
        scanf(" %s",G[y]);
        for(int x=0;x<C;x++){
            long yx1 = dj_find(yx(y,x));
            for(const auto& test:Z){
                if(test.edge == G[y][x]){
                    int ydest=y+test.dy, xdest=x+test.dx;
                    if(ydest<0||ydest==R||xdest<0||xdest==C){
                        if(!dj[yx1].escapes)
                            ans -= dj[yx1].count;
                        dj_escapes(yx1);
                    }else {
                        long yx2 = dj_find(yx(ydest,xdest));
                        if(yx1!=yx2){
                            //αφαίρεσε τις ομάδες από το ans πριν την ένωση αν χρειάζεται
                            if(!dj[yx1].escapes) ans-=dj[yx1].count;
                            if(!dj[yx2].escapes) ans-=dj[yx2].count;
                            //συνένωσε τις ομάδες
                            dj_union(yx1,yx2);
                            //ενημέρωσε το ans με την ενωμένη ομάδα αν χρειάζεται
                            yx1 = dj_find(yx1);
                            if(!dj[yx1].escapes) ans+=dj[yx1].count;
                        }
                    }
                }
            }//έλεγχος κατεύθυνσης ακμής εξόδου
        }//x (column)
    }//y (row)

Οι λειτουργίες union και find της union-find που χρησιμοποιούν συμπύκνωση μονοπατιών, χρειάζονται χρόνο \(\mathcal{O}(\alpha(N^2))\) ανα κλήση σε ένα δάσος \(N^2\) κόμβων σαν αυτό της άσκησης. Με \(\alpha(n)\) συμβολίζουμε την εξαιρετικά μικρής αύξησης ως προς το \(n\), αντίστροφη συνάρτηση Ackermann. Ενδεικτικά του ρυθμού αύξησης, το \(\alpha(9876 !)=5\). Στην πράξη, ο χρόνος στις συναρτήσεις union και find είναι σχεδόν γραμμικός λόγω του ότι το \(\alpha(n)\le 3\) για οποιοδήποτε \(n\) μπορεί να προκύψει στην πράξη ανφ.R.Tarjan. ↩