Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <vector>
- #include <algorithm>
- #include <cstring>
- using namespace std;
- struct node{
- int x;
- int y;
- int distance;
- node(){
- }
- node(int _x, int _y, int _distance){
- x=_x;
- y=_y;
- distance=_distance;
- }
- bool operator <(const node& temp)const{
- return distance<temp.distance;
- }
- };
- int main()
- {
- int n, m;
- cin>>n;
- cin>>m;
- char matrica[n][m];
- bool visited[n][m];
- int sy;
- int sx;
- int ex;
- int ey;
- int distance[n][m];
- vector<pair<int, int>>v;
- priority_queue<node>pq;
- queue<int>q;
- for(int y=0; y<n; y++){
- for(int y1=0; y1<m; y1++){
- visited[y][y1]=false;
- }
- }
- for(int x=0; x<n; x++){
- for(int x1=0; x1<m; x1++){
- cin>>matrica[x][x1];
- if(matrica[x][x1]=='G'){
- q.push(x);
- q.push(x1);
- q.push(0);
- }
- if(matrica[x][x1]=='R'){
- sx=x;
- sy=x1;
- }
- if(matrica[x][x1]=='Z'){
- ex=x;
- ey=x1;
- }
- }
- }
- for(int h=0; h<n; h++){
- for(int h1=0; h1<m; h1++){
- distance[h][h1]=-1;
- }
- }
- int dx[]={1,0,-1,0};
- int dy[]={0,1,0,-1};
- while(!q.empty()){
- int cx=q.front();
- q.pop();
- int cy=q.front();
- q.pop();
- int brojac=q.front();
- q.pop();
- if(matrica[cx][cy]=='G'){
- distance[cx][cy]=0;
- visited[cx][cy]=true;
- }
- for(int y=0; y<4; y++){
- int tx=cx+dx[y];
- int ty=cy+dy[y];
- if((tx>=0)and(ty>=0)and(tx<n)and(ty<m)and(visited[tx][ty]==false)and(matrica[tx][ty]!='*')){
- q.push(tx);
- q.push(ty);
- visited[tx][ty]=true;
- distance[tx][ty]=brojac+1;
- q.push(brojac+1);
- }
- }
- }
- for(int d=0; d<n; d++){
- for(int d1=0; d1<m; d1++){
- visited[d][d1]=false;
- cout << distance[d][d1] << " " ;
- }
- cout << endl;
- }
- pq.push(node(sx, sy, distance[sx][sy]));
- while(!pq.empty()){
- node c=pq.top();
- pq.pop();
- if((c.x==ex)and(c.y==ey)){
- cout<<c.distance;
- return 0;
- }
- for(int d2=0; d2<4; d2++){
- int tx=c.x+dx[d2];
- int ty=c.y+dy[d2];
- if((ty>=0)and(tx>=0)and(tx<n)and(ty<m)and(visited[tx][ty]==false)and(matrica[tx][ty]='.')){
- pq.push(node(tx, ty, min(distance[tx][ty], c.distance)));
- visited[tx][ty]=true;
- }
- }
- }
- return 0;
- }
- /*
- 4 3 2 3 4 3 2 3 4
- 3 2 1 2 3 2 1 2 3
- 2 1 0 1 2 1 0 1 2
- 1 2 1 2 2 2 1 2 3
- 0 1 2 2 1 2 2 3 4
- 1 2 2 1 0 1 2 3 4
- 2 3 3 -1 -1 2 3 4 5
- 3 4 4 5 4 3 4 5 6
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement