Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #define INF (1<<29)
- using namespace std;
- int dx[] = {-1, 1, 0, 0};
- int dy[] = { 0, 0, 1,-1};
- struct graf {
- vector< string > ady;
- vector < vector<int> > dist;
- int n, inicialX, inicialY, finalX, finalY;
- int x, y;
- void leer()
- {
- cin>>n;
- ady.resize(n+1);
- dist = vector< vector<int> > (n+1, vector<int> (n+1, INF) );
- string a;
- for(int i=0; i<n; i++)
- {
- cin>>a;
- ady[i]=a;
- }
- cin>>inicialX>>inicialY>>finalX>>finalY;
- }
- bool valid(const int &x, const int &y)
- {
- if ( 0<=x && x<=n && 0<=y && y<=n && ady[x][y]!='X')
- return true;
- return false;
- }
- bool mover (int x, int y, int dx, int dy, int &topex, int &topey)
- {
- int newx = x+dx;
- int newy = y+dy;
- if ( valid(newx,newy) )
- {
- if ( dist[x][y]+1 < dist[newx][newy] )
- dist[newx][newy] = dist[x][y]+1;
- mover(newx,newy,dx,dy,topex,topey);
- }
- else
- {
- topex=x;
- topey=y;
- }
- }
- int BFS ()
- {
- queue< pair<int,int> > q;
- x = inicialX;
- y = inicialY;
- q.push( {x,y} );
- dist[x][y]=0;
- while( q.size()!=0 )
- {
- x = q.front().first;
- y = q.front().second;
- q.pop();
- for (int i=0; i<4; i++)
- {
- int topex, topey;
- mover(x,y,dx[i],dy[i],topex,topey);
- if( dist[x][y]+1 < dist[topex][topey] )
- {
- dist[topex][topey] = dist[x][y]+1;
- q.push( {topex,topey} );
- }
- }
- }
- return dist[finalX][finalY];
- }
- };
- int main()
- {
- graf g;
- g.leer();
- cout<<g.BFS();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment