#include #include #include #include using namespace std; #define MAX_R 1024 // dimensione massima del labirinto #define MAX_M 102400 // massimo numero previsto di mosse // shorcut per creare una struttura di tipo pos #define makepos(TikR,TikC,TokR,TokC) make_pair( make_pair(TikR,TikC), make_pair(TokR, TokC) ) typedef pair< pair, pair > pos; // tipo "posizione" con i 4 campi per la posizione dei due robot char Labirinto[MAX_R][MAX_R]; // il labirinto map Parent; // mappa che dice per ogni posizione da dove mi conveniva arrivarci. // se una posizione non c'e, vuol dire che non l'ho ancora visitata pos invalid = makepos(-1,-1,-1,-1); // costante che significa: "posizione invalida" ///////////////////////////////////////////////////////// bool hovinto( pos P ) // funzione che verifica se P e' una posizione vincente: { // devono essere entrambi su una 'O' ed essere in posizioni diverse return ( Labirinto[P.first.first][P.first.second] == 'O' && Labirinto[P.second.first][P.second.second] == 'O' && !(P.first == P.second) ); } pos move( pos start, int NS, int EO ) // funzione che attua una mossa sulla posizione start { if ( Labirinto[start.first.first +NS][start.first.second +EO] == 'X' ) return invalid; // in questo caso, facendo if ( Labirinto[start.second.first+NS][start.second.second+EO] == 'X' ) return invalid; // la mossa perdo la partita pos next = start; if ( Labirinto[start.first.first +NS][start.first.second +EO] != '#' ) { // se vado su un muro non mi muovo, altrimenti: next.first.first += NS; next.first.second += EO; } if ( Labirinto[start.second.first +NS][start.second.second +EO] != '#' ) { // idem per l'altro robot next.second.first += NS; next.second.second += EO; } return next; } ///////////////////////////////////////////////////////// pos visita_bfs( pos Iniziale ) // procedura che esamina tutte le mosse data la posizione iniziale { // e restituisce la posizione finale della sequenza di mosse queue DaVisitare; // Per trovare la sequenza minima, faccio una visita BFS del grafo delle mosse pos Current = invalid, Next = invalid; DaVisitare.push( Iniziale ); // metto nella coda delle cose da visitare la posizione iniziale, Parent[Iniziale] = invalid; // segnandomi che non ha un parent: in questo modo quando ricostruisco mi accorgo di essere arrivato all'inizio while (!DaVisitare.empty()) { // finche' ci sono cose da visitare, le visito Current = DaVisitare.front(); DaVisitare.pop(); if ( hovinto(Current) ) { // se ho vinto, esco restituendo la posizione in cui ho vinto return Current; } Next = move( Current, +1, 0 );// altrimenti provo le 4 mosse possibili una per volta if ( !( Next == invalid ) && Parent.find( Next ) == Parent.end() ) { // e me le segno da visitare se sono valide e non gia' considerate DaVisitare.push( Next ); Parent[Next] = Current; } Next = move( Current, -1, 0 ); if ( !( Next == invalid ) && Parent.find( Next ) == Parent.end() ) { DaVisitare.push( Next ); Parent[Next] = Current; } Next = move( Current, 0, +1 ); if ( !( Next == invalid ) && Parent.find( Next ) == Parent.end() ) { DaVisitare.push( Next ); Parent[Next] = Current; } Next = move( Current, 0, -1 ); if ( !( Next == invalid ) && Parent.find( Next ) == Parent.end() ) { DaVisitare.push( Next ); Parent[Next] = Current; } } return invalid; } ///////////////////////////////////////////////////////// void print( pos finale ) { char Mosse[MAX_M]; // vettore contenente la sequenza di mosse da stampare int nMosse = 0; pos Current = finale; pos Next = invalid; if ( finale == invalid ) { // se ho fallito, stampo -1 cout << -1 << endl; return; } Next = Parent[Current]; while ( !( Next == invalid ) ) { // altrimenti parto dalla fine, e risalgo a quale mossa avevo fatto nella visita per arrivare a ogni posizione if ( move(Next, +1, 0) == Current ) Mosse[nMosse++] = 'S'; else if ( move(Next, -1, 0) == Current ) Mosse[nMosse++] = 'N'; else if ( move(Next, 0, +1) == Current ) Mosse[nMosse++] = 'E'; else if ( move(Next, 0, -1) == Current ) Mosse[nMosse++] = 'O'; else cerr << "Questo non dovrebbe succedere." << endl; // controllo di debug Current = Next; Next = Parent[Current]; } cout << nMosse << endl; for (int i=nMosse-1; i>=0; i--) { // a questo punto posso stampare le mosse in ordine contrario a quanto trovato cout << Mosse[i]; } cout << endl; } int main() { char row[MAX_R]; int R, C, TikR, TikC, TokR, TokC; cin >> R >> C >> TikR >> TikC >> TokR >> TokC; // leggo l'input for (int i=1; i<=R; i++) { cin >> row; // leggo una riga del labirinto for (int j=1; j<=C; j++) { Labirinto[i][j] = row[j-1]; // e la ricopio nel vettore } } for (int i=1; i<=R; i++) Labirinto[i][0] = Labirinto[i][C+1] = '#'; // creo una cornice di caselle con muri # for (int i=1; i<=C; i++) Labirinto[0][i] = Labirinto[R+1][i] = '#'; // intorno al labirinto letto, per evitare sconfinamenti print( visita_bfs( makepos( TikR, TikC, TokR, TokC ) ) ); // risolvo il problema e faccio stampare la soluzione return 0; }