#include using namespace std; int n,m,viz[150][150]; int vizEnd[150][150]; int inQueue[150][150]; char s[150]; vector > poz; vector > endpoz; pair start; int dx[]={1,-1,0,0}; int dy[]={0,0,-1,1}; int distEnd[150][150],vizStart[150][150],vizCurrent[150][150]; bool insideNM (pair acum) { // aici verific si daca pot ajunge acolo if (1<=acum.first && acum.first <=n && 1<=acum.second && acum.second <=m && viz[acum.first][acum.second] != -1) return true; return false; } set > currentPositions; vector > neighbours(pair acum) { vector > answer; for (int i=0;i<4;i++) { pair neighbour = {acum.first+dx[i],acum.second+dy[i]}; if (insideNM(neighbour)==true && vizCurrent[neighbour.first][neighbour.second] == 0 && distEnd[neighbour.first][neighbour.second]>=0) answer.push_back(neighbour); } return answer; } vector > neighboursLigma(pair acum) { vector > answer; for (int i=0;i<4;i++) { pair neighbour = {acum.first+dx[i],acum.second+dy[i]}; if (insideNM(neighbour)==true && vizCurrent[neighbour.first][neighbour.second] == 1 && distEnd[neighbour.first][neighbour.second]>=0) answer.push_back(neighbour); } return answer; } int vizHello[150][150]; bool wouldntDisc(pair currentCell) { pair start; vector> neighboursNow = neighboursLigma(currentCell); for (int i=0;i> q; q.push(start); int nr=1; while (!q.empty()) { auto acum = q.front(); q.pop(); vector> neighboursNow = neighboursLigma(acum); for (int i=0;i> n>>m; cin.get(); for (int i=1;i<=n;i++) { cin.getline(s,m+5); for (int k=0;k > q; q.push(start); for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { vizEnd[i][j]=0; inQueue[i][j]=0; } } vizEnd[start.first][start.second]=1; while (!q.empty()) { pair acum = q.front(); q.pop(); inQueue[acum.first][acum.second]=0; for (int i=0;i<4;i++) { pair vecin ={acum.first+dx[i],acum.second+dy[i]}; if (insideNM(vecin) == true && vizEnd[vecin.first][vecin.second] == 0 && inQueue[vecin.first][vecin.second] == 0) { vizEnd[vecin.first][vecin.second]=1; inQueue[vecin.first][vecin.second]=1; q.push(vecin); } } } for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { distEnd[i][j]=-1; inQueue[i][j]=0; } } for (int i=0;i acum = q.front(); q.pop(); inQueue[acum.first][acum.second]=0; for (int i=0;i<4;i++) { pair vecin ={acum.first+dx[i],acum.second+dy[i]}; if (insideNM(vecin) == true && inQueue[vecin.first][vecin.second] == 0 && (distEnd[vecin.first][vecin.second] == -1 || distEnd[vecin.first][vecin.second] > distEnd[acum.first][acum.second]+1 )) { distEnd[vecin.first][vecin.second] = distEnd[acum.first][acum.second]+1; inQueue[vecin.first][vecin.second]=1; q.push(vecin); } } } while (!q.empty()) q.pop(); for (int i=0;i acum = q.front(); q.pop(); inQueue[acum.first][acum.second]=0; for (int i=0;i<4;i++) { pair vecin ={acum.first+dx[i],acum.second+dy[i]}; if (insideNM(vecin) == true && vizStart[vecin.first][vecin.second] == 0 && inQueue[vecin.first][vecin.second] == 0) { vizStart[vecin.first][vecin.second]=1; inQueue[vecin.first][vecin.second]=1; q.push(vecin); } } } for (int i=0;i> , vector >> , greater > > > heapie; priority_queue >> heapie2; for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { viz[i][j]=0; } } int nrLeft = endpoz.size(); for (int i=0;i> neighboursNow = neighbours(poz[i]); heapie2.push({distEnd[poz[i].first][poz[i].second],poz[i]}); for (int j=0;j,pair>> answer; // That means I have not covered the final positions // Otherwise all neighbours would have distance 1 while (!heapie.empty() && nrLeft>0) { while (!heapie.empty() && (viz[heapie.top().second.first][heapie.top().second.second] == 0 || vizCurrent[heapie.top().second.first][heapie.top().second.second] == 1)) { heapie.pop(); } if (heapie.empty()) break; pair currentCell = heapie.top().second; vector > gotOut; if (poz.size()!=2) { while (!heapie2.empty() && wouldntDisc(heapie2.top().second) == false) { gotOut.push_back(heapie2.top().second); heapie2.pop(); } } if (heapie2.empty()) break; pair farthestAway = heapie2.top().second; heapie2.pop(); for (int i=0;i> neighboursNow = neighbours(farthestAway); for (int j=0;j