#include using namespace std; int n,m,viz[30][30]; int vizEnd[30][30]; int inQueue[30][30]; char s[30]; vector > poz; vector > endpoz; pair start; int dx[]={1,-1,0,0}; int dy[]={0,0,-1,1}; int distEnd[30][30],vizStart[30][30],vizCurrent[30][30]; 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; } int main() { ios_base :: sync_with_stdio(false); cin.tie(0); cin >> 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=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); } } } 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; pair farthestAway = heapie2.top().second; heapie2.pop(); heapie.pop(); answer.push_back({farthestAway,currentCell}); vector > neighboursNow = neighbours(farthestAway); for (int j=0;j