33ος ΠΔΠ Γ' Φάση: Γυρίζοντας στο σπίτι (wayhome) - Λύση

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

Εισαγωγή

Έχουμε ένα γράφο με μορφή πλέγματος (grid) και η κίνηση γίνεται οριζόντια και κάθετα στους διπλανούς κόμβους. Ενδέχεται να υπάρχουν απαγορευμένοι κόμβοι (κτίρια). Στο γράφο αυτό κινούμαστε ταυτόχρονα με έναν αστυνομικό και θέλουμε να φτάσουμε στην έξοδο (σπίτι) χωρίς να καταφέρει ο αστυνομικός να μας δει. Δεν ξέρουμε ποια διαδρομή θα ακολουθήσει ο αστυνομικός και πρέπει να σχεδιάσουμε τη διαδρομή σύμφωνα με την πιο απαισιόδοξη για εμάς κίνηση του αστυνομικού.

Λύση με απλή μέτρηση αποστάσεων (17% της βαθμολογίας)

Στο subtask αυτό δεν υπάρχουν εμπόδια.

Παρατήρηση 1: μας ενδιαφέρει μόνο αν ο αστυνομικός εποπτεύσει το σπίτι μας πριν φτάσουμε εμείς εκεί. Αρκεί δηλαδή να μετακινηθεί μόνο οριζόντια ή μόνο κάθετα ώστε να φτάσει στη γραμμή ή στήλη του σπιτιού. Στο παρακάτω σχήμα, από τις δύο πορτοκαλί θέσεις, θα διαλέξει αυτή με τη συντομότερη διαδρομή.

Απόδειξη: Έστω \(R_\mathit{home}\) η γραμμή και \(C_\mathit{home}\) η στήλη του σπιτιού. Έστω ότι ο αστυνομικός θα μπορέσει να μας δει καθώς περνάμε από τη στήλη¹ \(C_\mathit{you}\), πριν φτάσουμε στο σπίτι, την ώρα που θα βρισκόμαστε στο σημείο \((R_\mathit{you},C_\mathit{you})\). Τότε για τον αστυνομικό, ο απαιτούμενος χρόνος να φτάσει από τη στήλη \(C_\mathit{you}\) στη στήλη επόπτευσης του σπιτιού, είναι \(t_\mathit{pol} = |C_\mathit{home} - C_\mathit{you}|\) ενώ για εμάς είναι \(t_\mathit{you} = |C_\mathit{home} - C_\mathit{you}| + |R_\mathit{home}-R_\mathit{you}| \Rightarrow t_\mathit{you} = t_\mathit{pol} + |R_\mathit{home}-R_\mathit{you}|\).
Ισχύει ότι \(|R_\mathit{home}-R_\mathit{you}| \ge 0\), οπότε από την προηγούμενη ισότητα προκύπτει ότι \(t_\mathit{you} \ge t_\mathit{pol}\).

Άρα αν ο αστυνομικός μπορεί να μας δει σε οποιοδήποτε σημείο της διαδρομής μας, θα μας δει και την ώρα που φτάνουμε στο σπίτι. Οπότε για να λύσουμε το subtask αυτό, αρκεί να ελέγξουμε αν μπορούμε να φτάσουμε στο σπίτι πριν το εποπτεύσει ο αστυνομικός.

Παρατήρηση 2: Εμείς θα πρέπει να κινηθούμε όσο γρηγορότερα γίνεται για να φτάσουμε στο σπίτι. Άρα δεν συμφέρει να κάνουμε περιττά βήματα ώστε να αποφύγουμε τον αστυνομικό καθώς θα χάσουμε περισσότερο χρόνο και δεν θα μπορέσουμε να μπούμε με ασφάλεια στο σπίτι.

Η διαδρομή που θα κάνουμε εμείς, θα είναι μια ευθύγραμμη κίνηση (αν βρισκόμαστε στην ίδια γραμμή ή στήλη με το σπίτι) ή δυο ευθύγραμμες κινήσεις (μια οριζόντια και μια κατακόρυφη). Το άθροισμα της κατακόρυφης και οριζόντιας απόστασης που θα διανύσουμε, ονομάζεται απόσταση Manhattan. Για παράδειγμα, στο παρακάτω σχήμα χρειαζόμαστε 3 βήματα για να φτάσουμε σπίτι ενώ γιά τον αστυνομικό αρκεί 1 μόνο βήμα για να φτάσει στη γραμμή του σπιτιού και να μας περιμένει εκεί.

Παράδειγμα απόστασης Manhattan

Ο υπολογισμός της απάντησης γίνεται σε \(\mathcal{O}(1)\) χρόνο. Η συνολική πολυπλοκότητα είναι \(\mathcal{O}(N\cdot M)\) λόγω της ανάγνωσης των δεδομένων εισόδου.

#include <cstdio>
#include <algorithm>
#include <queue>
#include <climits>
using namespace std;

const int MAXNM = 700;
struct pt {
    int x,y;
    pt(int x=0,int y=0):x(x),y(y){}
} ho,po,yo;//ho(me),po(liceman),yo(u)
int T,XM,YN;//XM=στήλες, YN=γραμμές

bool go_home(){
    int po_time = min(abs(po.x-ho.x),abs(po.y-ho.y));
    int yo_time = abs(yo.x-ho.x) + abs(yo.y-ho.y);
    return yo_time<po_time;
}

int main(){
    freopen("wayhome.in", "r",stdin);
    freopen("wayhome.out","w",stdout);
    scanf("%d",&T);
        
    while(T--){
        scanf("%d%d",&YN,&XM);
        for(int y=1;y<=YN;y++){
            char s[MAXNM+1];
            scanf(" %s",s);
            for(int x=1;x<=XM;x++){
                switch(s[x-1]){
                    case 'Y': yo = pt(x,y); break;
                    case 'P': po = pt(x,y); break;
                    case 'H': ho = pt(x,y); break;
                }
            }
        }
        printf(go_home()?"YES\n":"NO\n");
    }
    return 0;
}

Λύση με διπλό bfs και ενημέρωση γραμμών/στηλών με βρόγχο (42% της βαθμολογίας)

Θα κάνουμε δυο διασχίσεις του γράφου, μια για τον αστυνομικό και μια για εμάς. Στην πρώτη διάσχιση, ο αστυνομικός μπορεί να επισκεφτεί κάθε κελί ή να το εποπτεύσει από απόσταση αν οριζόντια ή κάθετα από τη θέση του δεν παρεμβάλλεται κτίριο. Στόχος μας είναι να υπολογίσουμε τον ελάχιστο χρόνο που χρειάζεται ο αστυνομικός για να φτάσει σε κάθε κελί και τον ελάχιστο χρόνο για να εποπτεύσει το κάθε κελί. Επόμενο βήμα είναι να προσπαθήσουμε να φτάσουμε από τη θέση που βρισκόμαστε εμείς, στο κελί τερματισμού, περνώντας από οποιαδήποτε κελιά απαιτείται, αρκεί να τα επισκεφτούμε πριν το χρόνο που ο αστυνομικός μπορεί να τα επισκεφτεί η τα εποπτεύσει.

Εφόσον έχει σημασία να μετράμε τα βήματα μας από την αρχική θέση, θα ακολουθήσουμε μέθοδο bfs (αναζήτηση κατά πλάτος) ώστε να εξερευνούμε πρώτα όλες τις κινήσεις μια τιμής χρόνου (βάθους) \(i\) πριν πάμε στην επόμενη \(i+1\).

Εκτελούμε ένα bfs για τον αστυνομικό και σε κάθε θέση που φτάνει, ενημερώνουμε τα κελιά της οριζόντιας και κατακόρυφης ακμής για το χρόνο επόπτευσης. Το bfs έχει πολυπλοκότητα \(\mathcal{O}(N\cdot M)\) και για κάθε ένα κελί που επισκεπτόμαστε, θα χρειαστούμε επιπλέον \(\mathcal{O}(N+M)\) χρόνο για τις ενημερώσεις. Συνολική πολυπλοκότητα \(\mathcal{O}(N\cdot M\cdot (N+M))\)

#include <cstdio>
#include <algorithm>
#include <queue>
#include <climits>
using namespace std;

const int MAXNM = 700;
struct pt {
    int x,y;
    pt(int x=0,int y=0):x(x),y(y){}
} ho,po,yo;//ho(me),po(liceman),yo(u)
int T,XM,YN;//XM=στήλες, YN=γραμμές

struct cell {
    bool pol_visit;   //επίσκεψη αστυνομικού
    long view; //ώρες θέασης κελιού
    bool you_visit; //δικιά μας επίσκεψη
    char c;//χαρακτηριστικό κελιού του grid
    
    void init(){ 
        c = '#';//εκτός grid 
        view = LONG_MAX; 
        pol_visit = you_visit = false; 
    }
    inline bool is_road() const { return c != '#'; }
    inline bool is_home() const { return c == 'H'; }
} G[MAXNM+2][MAXNM+2];//grid
/*
 * Το grid του προβλήματος εκτείνεται από 
 * θέση (1,1) έως (Ν,Μ). Δεσμεύονται οι περιμετρικές γραμμές του
 * grid ώστε να γίνεται εύκολος ο έλεγχος στα άκρα.
 * Οι περιμετρικές γραμμές έχουν '#' (building)
 * οπότε γίνεται απλός ο έλεγχος αν μια θέση βρίσκεται εντός ή εκτός grid.
 * Λόγω των επιπλέον περιμετρικών γραμμών, ο πίνακας μας απαιτεί 2 επιπλέον
 * στοιχεία, οπότε δεσμεύεται ως G[MAXNM+2][MAXNM+2]
 */

//Κίνηση αστυνομικού
void pol_go(queue<pt>& Q,int x,int y){//επόμενο βήμα αστυνόμου
    if(G[x][y].is_road() && !G[x][y].pol_visit)
        Q.push(pt(x,y)), G[x][y].pol_visit = true;
}
void update_view(int x0,int y0,long tim){
    for(int x=x0;G[x][y0].is_road();x--)
        G[x][y0].view = min(G[x][y0].view,tim);
    for(int x=x0+1;G[x][y0].is_road();x++)
        G[x][y0].view = min(G[x][y0].view,tim);
    
    for(int y=y0;G[x0][y].is_road();y--)
        G[x0][y].view = min(G[x0][y].view,tim);
    for(int y=y0+1;G[x0][y].is_road();y++)
        G[x0][y].view = min(G[x0][y].view,tim);
}
void pol_bfs(){//bfs αστυνόμου
    queue<pt> Q;
    Q.push(po);
    long tim = 0;//time stamp
    while(!Q.empty()){
        for(size_t sz = Q.size(),i=0;i<sz;i++){
            int x = Q.front().x, y = Q.front().y; Q.pop();
            update_view(x,y,tim);
            //επισκέψου τα επόμενα κελιά
            pol_go(Q,x+1,y);
            pol_go(Q,x-1,y);
            pol_go(Q,x,y+1);
            pol_go(Q,x,y-1);
        }
        tim++;
    }
}

//Κίνηση δικιά μας
void you_go(queue<pt>& Q,int x,int y,int tim){//επόμενο βήμα δικό μας
    if(G[x][y].is_road() && !G[x][y].you_visit && tim<G[x][y].view )
        Q.push(pt(x,y)), G[x][y].you_visit = true;
}

bool you_bfs(){
    queue<pt> Q;
    Q.push(yo);
    long tim = 0;
    while(!Q.empty()){
        tim++;//σε αυτό το χρόνο θα γίνουν οι επομενες κινησεις
        for(size_t sz = Q.size(),i=0;i<sz;i++){
            int x = Q.front().x, y = Q.front().y; Q.pop();
            if(G[x][y].is_home())
                return true;
            you_go(Q,x+1,y,tim);
            you_go(Q,x-1,y,tim);
            you_go(Q,x,y+1,tim);
            you_go(Q,x,y-1,tim);
        }
    }
    return false;
}

void init(){//αρχικοποίηση για νεο σεναριο
    for(int y=0,yn=YN+2;y<yn;y++)
        for(int x=0,xm=XM+2;x<xm;x++)
            G[x][y].init();
}

int main(){
    freopen("wayhome.in", "r",stdin);
    freopen("wayhome.out","w",stdout);
    scanf("%d",&T);
        
    while(T--){
        scanf("%d%d",&YN,&XM);
        init();
        for(int y=1;y<=YN;y++){
            char s[MAXNM+1];
            scanf(" %s",s);
            for(int x=1;x<=XM;x++){
                switch(G[x][y].c = s[x-1]){
                    case 'Y': yo = pt(x,y); break;
                    case 'P': po = pt(x,y); break;
                    case 'H': ho = pt(x,y); break;
                }
            }
        }
        pol_bfs();
        printf(you_bfs()?"YES\n":"NO\n");
    }
    return 0;
}

Λύση με απόδοση εκπροσώπων + bfs (100% της βαθμολογίας)

Στην προηγούμενη λύση για κάθε κελί που επισκεπτόταν ο αστυνομικός, ενημερώναμε τους χρόνους θέασης των κελιών της οριζόντιας και κατακόρυφης γραμμής και καταλήγαμε σε πολυπλοκότητα της τάξης \(\mathcal{O}(N^3)\).

Παρατήρηση 2: Ας θεωρήσουμε ότι σε οποιαδήποτε θέση \(x,y\) έχουμε “δρόμο”. Ας ορίσουμε την οριζόντια ομάδα που περιέχει τη θέση \(x,y\), ως όλα τα συνεχόμενα κελιά, αριστερά και δεξιά της \(x,y\) που δεν περιέχουν κτίριο. Όλα τα κελιά της ομάδας αυτής, θα τα εποπτεύσει ταυτόχρονα ο αστυνομικός μόλις φτάσει σε οποιοδήποτε από αυτά και αρκεί σε κάθε ομάδα να έχουμε αποδώσει έναν εκπρόσωπο για να ενημερώνουμε σε χρόνο \(\mathcal{O}(1)\) τη χρονική στιγμή που ο αστυνομικός θα τα εποπτεύσει.

Μπορούμε να χρησιμοποιήσουμε μια παραλλαγή του αλγορίθμου flood fill² για να αποδώσουμε εκπροσώπους στα κελιά. Κάνουμε ένα διπλό (nested) loop ώστε για κάθε κελί που δεν έχει εκπροσώπους, να του αποδώσουμε έναν νέο και ταυτόχρονα ενημερώνουμε όλα τα κελιά της ομάδας του ότι έχουν τον ίδιο εκπρόσωπο. Σε κάθε κελί που αποκτά εκπρόσωπο θα χρειαστεί να ενημερώσουμε έως \(N+M\) ακόμα κελιά (τα συνευθειακά του οριζόντια ή κατακόρυφα). Σε κάθε κελί όμως θα αποδοθεί το πολύ μια φορά εκπρόσωπος άρα η απόδοση εκπροσώπων έχει amortized πολυπλοκότητα \(\mathcal{O}(N\cdot M)\). Συνολική πολυπλοκότητα λύσης: \(\mathcal{O}(N\cdot M)\).

Παράδειγμα απόδοσης εκπροσώπων

Η απόδοση εκπροσώπων γίνεται με τον παρακάτω κώδικα:

void fill_horz(int x,int y,int delta,size_t prx){
    //ενημέρωσε την οριζόντια ομάδα για τον εκπρόσωπο
    while(G[x][y].is_road())
        G[x][y].hpr = prx, x+=delta;
}
void fill_vert(int x,int y,int delta,size_t prx){
    //ενημέρωσε την κατακόρυφη ομάδα για τον εκπρόσωπο
    while(G[x][y].is_road())
        G[x][y].vpr = prx, y+=delta;
}
    
void assign_proxy(){//απόδοση εκπροσώπων
    size_t count = 0;
    for(int y=1;y<=YN;y++){
        for(int x=1;x<=XM;x++){
            if(!G[x][y].is_road())
                continue;
            if(G[x][y].hpr == -1L){
                proxy[count] = LONG_MAX;
                fill_horz(x,y,1,count);
                fill_horz(x,y,-1,count);
                count++;
            }
            if(G[x][y].vpr == -1L){
                proxy[count] = LONG_MAX;
                fill_vert(x,y,1,count);
                fill_vert(x,y,-1,count);
                count++;
            }
        }
    }
}

Η bfs του αστυνομικού:

    while(!Q.empty()){
        for(size_t sz = Q.size(),i=0;i<sz;i++){
            int x = Q.front().x, y = Q.front().y; Q.pop();
            //ενημέρωσε ώρες θέασης της ομάδας
            proxy[G[x][y].hpr] = min(proxy[G[x][y].hpr], tim);
            proxy[G[x][y].vpr] = min(proxy[G[x][y].vpr], tim);
            //επισκέψου τα επόμενα κελιά
            pol_go(Q,x+1,y);
            pol_go(Q,x-1,y);
            pol_go(Q,x,y+1);
            pol_go(Q,x,y-1);
        }
        tim++;
    }

Η bfs της δικής μας κίνησης:

    while(!Q.empty()){
        tim++;//σε αυτό το χρόνο θα γίνουν οι επομενες κινησεις
        for(size_t sz = Q.size(),i=0;i<sz;i++){
            int x = Q.front().x, y = Q.front().y; Q.pop();
            if(G[x][y].is_home())
                return true;
            you_go(Q,x+1,y,tim);
            you_go(Q,x-1,y,tim);
            you_go(Q,x,y+1,tim);
            you_go(Q,x,y-1,tim);
        }
    }

Δείτε ολόκληρο τον κώδικα εδώ

Συμτομότερος κώδικας απόδοσης εκπροσώπων + bfs (100% της βαθμολογίας)

Για κάθε κελί ορίζουμε σαν εκπρόσωπο οριζόντιας επόπτευσης το αριστερότερο ορατό κελί και σαν εκπρόσωπο κατακόρυφης επόπτευσης το υψηλότερο κατακόρυφο ορατό κελί. Η απόδοση εκπροσώπων για κάθε κελί γίνεται σε χρόνο \(\mathcal{O}(1)\). Η συνολική πολυπλοκότητα της λύσης είναι: \(\mathcal{O}(N\cdot M)\).

        vector<int> left(YN+2,1), top(XM+2,1);
        for(int y=1;y<=YN;y++){
            char s[MAXNM+1];
            scanf(" %s",s);
            for(int x=1;x<=XM;x++){
                switch(cell[x][y] = s[x-1]){
                    case 'Y': yo = {x,y}; break;
                    case 'P': po = {x,y}; break;
                    case 'H': ho = {x,y}; break;
                    case '#'://βρέθηκε κτίριο
                            top [x] = y+1;//ενημέρωσε το τρέχον αριστερότερο
                            left[y] = x+1;//και κορυφαίο ορατό κελί
                            break;
                }
                if(is_road(x,y)){//ενημέρωσε το κελί για τους 2 εκπροσώπους του
                    leftmost[x][y] = left[y];
                    topmost [x][y] = top [x];
                }
            }
        }

Δείτε ολόκληρο τον κώδικα εδώ

Αντίστοιχη είναι η απόδειξη αν μας δει στη γραμμή \(R_\mathit{you}\). ↩
Εναλλακτικά μπορούμε να χρησιμοποιήσουμε και τη δομή union-find για να αποδώσουμε εκπροσώπους. Σε κάθε κελί θα υπάρχει ο οριζόντιος και κατακόρυφος εκπρόσωπος. Καθώς ο αστυνομικός εξερευνεί κελιά, θα γίνεται και η συνένωση των κελιών σε ομάδες. Ο χρόνος επόπτευσης οποιαδήποτε οριζόντιας ή κατακόρυφης ομάδας, θα είναι ο μικρότερος χρόνος επίσκεψης σε οποιοδήποτε κελί της. ↩