Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- using namespace std;
- int main()
- {
- int n;
- int m;
- cin>>n>>m;
- char matrica[n][m];
- queue<int>q;
- queue<int>q1;
- int e1;
- int e2;
- int s1;
- int s2;
- int najgolem=0;
- int distance_s[n][m];
- int distance_e[n][m];
- for(int y=0; y<n; y++){
- for(int y1=0; y1<m; y1++){
- distance_s[y][y1]=-1;
- distance_e[y][y1]=-1;
- }
- }
- for(int x=0; x<n; x++){
- for(int x1=0; x1<m; x1++){
- cin>>matrica[x][x1];
- if(matrica[x][x1]=='E'){
- e1=x;
- e2=x1;
- }
- if(matrica[x][x1]=='S'){
- s1=x;
- s2=x1;
- }
- }
- }
- bool matrica1[n][m];
- for(int u=0; u<n; u++){
- for(int u1=0; u1<m; u1++){
- matrica1[u][u1]=false;
- }
- }
- bool matrica2[n][m];
- for(int u3=0; u3<n; u3++){
- for(int u2=0; u2<m; u2++){
- matrica2[u3][u2]=false;
- }
- }
- q.push(s1);
- q.push(s2);
- q.push(0);
- int niza1[]{0,0,-1,1};
- int niza2[]{-1,1,0,0};
- while(!q.empty()){
- int ts1=q.front();
- q.pop();
- int ts2=q.front();
- q.pop();
- int stapki=q.front();
- q.pop();
- if(matrica[ts1][ts2] == 'E') {
- cout << stapki << endl;
- return 0;
- }
- if(matrica[ts1][ts2]=='#'){
- distance_s[ts1][ts2]=stapki;
- continue;
- }
- for(int k1=0; k1<4; k1++){
- int cs1=ts1+niza1[k1];
- int cs2=ts2+niza2[k1];
- if((cs1>=0)and(cs1<n)and(matrica1[cs1][cs2]==false)and(cs2>=0)and(cs2<m)){
- q.push(cs1);
- q.push(cs2);
- q.push(stapki+1);
- matrica1[cs1][cs2]=true;
- }
- }
- }
- q1.push(e1);
- q1.push(e2);
- q1.push(0);
- while(!q1.empty()){
- int te1=q1.front();
- q1.pop();
- int te2=q1.front();
- q1.pop();
- int stapki1=q1.front();
- q1.pop();
- if(matrica[te1][te2]=='#'){
- distance_e[te1][te2]=stapki1;
- continue;
- }
- for(int k2=0; k2<4; k2++){
- int ce1=te1+niza1[k2];
- int ce2=te2+niza2[k2];
- if((ce1>=0)and(ce1<n)and(matrica2[ce1][ce2]==false)and(ce2>=0)and(ce2<m)){
- q1.push(ce1);
- q1.push(ce2);
- q1.push (stapki1+1);
- matrica2[ce1][ce2]=true;
- }
- }
- }
- for(int l=0; l<n; l++){
- for(int l1=0; l1<m; l1++){
- if((distance_e[l][l1]!=-1)and(distance_s[l][l1]!=-1)){
- int c1=distance_e[l][l1]+distance_s[l][l1];
- if(c1>najgolem){
- najgolem=c1;
- }
- }
- }
- }
- if(najgolem>0){
- cout<<najgolem;
- return 0;
- }
- cout<<"-1";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement