Zatvor

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    cin>>n>>m;

    int ri, rj, fi, fj;
    vector<pair<int, int> > govci;
    char matrix[n][m];
    int value[n][m];
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>matrix[i][j];
            if(matrix[i][j]=='#'){
                value[i][j]=-3;
                continue;
            }
            value[i][j]=98799697;
            if(matrix[i][j]=='R'){
                ri=i;
                rj=j;
            }
            if(matrix[i][j]=='Z'){
                fi=i;
                fj=j;
            }
            if(matrix[i][j]=='G')
                govci.push_back(make_pair(i, j));
        }
    }


    int g=govci.size();
    int diri[]={1, -1, 0, 0};
    int dirj[]={0, 0, 1, -1};
bool visited[n][m];
    for(int k=0; k<g; k++){
        queue <pair< int, int> > q;
        q.push(make_pair(govci[k].first, govci[k].second));

        memset(visited, 0, sizeof(visited));
        value[govci[k].first][govci[k].second]=0;
       // cout<<endl<<endl<<endl;
        while(!q.empty()){
            int ci=q.front().first;
            int cj=q.front().second;
            q.pop();
            visited[ci][cj]=1;
           // cout<<ci<<" "<<cj<<endl;
            for(int d=0; d<4; d++){
                int ni=ci+diri[d];
                int nj=cj+dirj[d];

                if(value[ni][nj]==-3) continue;
                if(ni>-1 && ni<n && nj>-1 && nj<m && visited[ni][nj]==0){
                    visited[ni][nj]=1;
                    value[ni][nj]=min(value[ci][cj]+1, value[ni][nj]);
                    q.push(make_pair(ni, nj));
                }
            }
        }
    }

//    for(int i=0; i<n; i++){
//        for(int j=0; j<m; j++){
//            cout<<value[i][j]<<"  ";
//            if(value[i][j]<10) cout<<" ";
//        }
//        cout<<endl;
//    }
    priority_queue<pair<int, pair<int, int> > > p;
    p.push(make_pair(value[ri][rj], make_pair(ri, rj)));
    memset(visited, 0, sizeof(visited));
    while(!p.empty()){

        int cd=p.top().first;
        int ci=p.top().second.first;
        int cj=p.top().second.second;
        p.pop();
        //cout<<ci<<" "<<cj<<" "<<cd<<endl;

        if(ci==fi && cj==fj){
            cout<<cd<<endl;

            return 0;
        }
        for(int d=0; d<4; d++){
            int ni=ci+diri[d];
            int nj=cj+dirj[d];
            if(matrix[ni][nj]=='*') continue;
            if(ni>-1 && ni<n && nj>-1 && nj<m && visited[ni][nj]==0){
                visited[ni][nj]=1;
                p.push(make_pair(min(cd, value[ni][nj]), make_pair(ni, nj)));
            }
        }
    }
    return 0;
}