SHARE
TWEET

Untitled

a guest Dec 9th, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int lli;
  4. int m[1001][1001],t[1001][1001],vis[1001][1001];
  5. int c,d;
  6. int dx[4]= {-1,0,0,1};
  7. int dy[4]= {0,-1,1,0};
  8. void bfs(int sx,int sy)
  9. {
  10.     int ux,uy,vx,vy;
  11.     queue<int>q;
  12.     q.push(sx);
  13.     q.push(sy);
  14.     vis[sx][sy]=1;
  15.     while(!q.empty())
  16.     {
  17.         ux=q.front();
  18.         q.pop();
  19.         uy=q.front();
  20.         q.pop();
  21.         for(int k=0; k<4; k++)
  22.         {
  23.             vx=ux+dx[k];
  24.             vy=uy+dy[k];
  25.  
  26.             if((vx>=0)&&(vx<=c)&&(vy>=0)&&(vy<=d)&&(!m[vx][vy])&&(!vis[vx][vy]))
  27.             {
  28.                 q.push(vx);
  29.                 q.push(vy);
  30.                 vis[vx][vy]=1;
  31.                 t[vx][vy]=t[ux][uy]+1;
  32.             }
  33.         }
  34.     }
  35. }
  36. int main()
  37. {
  38.     int e,row,mine,nom,sx,sy,ex,ey,ga,gb;
  39.     cin>>c>>d>>e;
  40.     while(e--)
  41.     {
  42.         cin>>row>>nom;
  43.         for(int i=1; i<=nom; i++)
  44.         {
  45.             cin>>mine;
  46.             m[row][mine]=1;
  47.         }
  48.     }
  49.  
  50.     cin>>sx>>sy;
  51.     bfs(sx,sy);
  52.     cin>>ex>>ey;
  53.     cin>>ga>>gb;
  54.     cout<<t[ex][ey]<<endl;
  55.     /*for(int i=0; i<c; i++)
  56.     {
  57.         for(int j=0; j<d; j++)
  58.         {
  59.             cout<<vis[i][j]<<" ";
  60.         }
  61.         cout<<endl;
  62.     }*/
  63.  
  64.  
  65.     return 0;
  66. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top