AlenAntonelli

Castle defectuosisimo

Jun 3rd, 2018
148
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.05 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #define INF (1<<29)
  5. using namespace std;
  6.  
  7. int dx[] = {-1, 1, 0, 0};
  8. int dy[] = { 0, 0, 1,-1};
  9.  
  10. struct graf {
  11.     vector< string > ady;
  12.     vector < vector<int> > dist;
  13.     int n, inicialX, inicialY, finalX, finalY;
  14.    
  15.     int x, y;
  16.    
  17.     void leer()
  18.     {
  19.         cin>>n;
  20.         ady.resize(n+1);
  21.         dist = vector< vector<int> > (n+1, vector<int> (n+1, INF) );
  22.        
  23.         string a;
  24.         for(int i=0; i<n; i++)
  25.         {
  26.             cin>>a;
  27.             ady[i]=a;
  28.         }
  29.         cin>>inicialX>>inicialY>>finalX>>finalY;
  30.     }
  31.    
  32.     bool valid(const int &x, const int &y)
  33.     {
  34.         if ( 0<=x && x<=n && 0<=y && y<=n && ady[x][y]!='X')
  35.             return true;
  36.         return false;
  37.     }
  38.    
  39.     bool mover (int x, int y, int dx, int dy, int &topex, int &topey)
  40.     {
  41.         int newx = x+dx;
  42.         int newy = y+dy;
  43.         if ( valid(newx,newy) )
  44.         {
  45.             if ( dist[x][y]+1 < dist[newx][newy] )
  46.                 dist[newx][newy] = dist[x][y]+1;
  47.             mover(newx,newy,dx,dy,topex,topey);
  48.         }
  49.         else
  50.         {
  51.             topex=x;
  52.             topey=y;
  53.         }
  54.     }
  55.    
  56.     int BFS ()
  57.     {
  58.         queue< pair<int,int> > q;
  59.        
  60.         x = inicialX;
  61.         y = inicialY;
  62.        
  63.         q.push( {x,y} );
  64.         dist[x][y]=0;
  65.        
  66.         while( q.size()!=0 )
  67.         {
  68.             x = q.front().first;
  69.             y = q.front().second;
  70.             q.pop();
  71.            
  72.             for (int i=0; i<4; i++)
  73.             {
  74.                 int topex, topey;
  75.                 mover(x,y,dx[i],dy[i],topex,topey);
  76.                
  77.                 if( dist[x][y]+1 < dist[topex][topey] )
  78.                 {
  79.                     dist[topex][topey] = dist[x][y]+1;
  80.                     q.push( {topex,topey} );
  81.                 }
  82.             }
  83.         }
  84.        
  85.         return dist[finalX][finalY];
  86.     }
  87. };
  88.  
  89. int main()
  90. {
  91.     graf g;
  92.     g.leer();
  93.     cout<<g.BFS();
  94.  
  95.     return 0;
  96. }
Advertisement
Add Comment
Please, Sign In to add comment