// B F S #include using namespace std; int state[205][205]; pair par[205][205]; int dis[205][205]; #define initial 1 #define waiting 2 #define visited 3 #define NIL -1 #define infinity 10000000 int n; stack s; bool check(int x,int y){ if(x>=0 && x<=n-1 && y>=0 && y<=n-1) return true; else return false; } void bfs(int x,int y) // Doing just bfs , not calculating anything just traversing { queue < pair > q; q.push(make_pair(x,y)); state[x][y]=waiting; par[x][y].first=NIL; par[x][y].second=NIL; dis[x][y]=0; while(!q.empty()) { pair p=q.front(); q.pop(); state[p.first][p.second]=visited; int x=p.first; int y=p.second; if( check(x-2,y-1) && state[x-2][y-1]==initial ){ q.push(make_pair(x-2,y-1)); state[x-2][y-1]=waiting; par[x-2][y-1].first=p.first; par[x-2][y-1].second=p.second; dis[x-2][y-1]=dis[par[x-2][y-1].first][par[x-2][y-1].second] + 1; } if( check(x-2,y+1) && state[x-2][y+1]==initial ){ q.push(make_pair(x-2,y+1)); state[x-2][y+1]=waiting; par[x-2][y+1].first=p.first; par[x-2][y+1].second=p.second; dis[x-2][y+1]=dis[par[x-2][y+1].first][par[x-2][y+1].second] + 1; } if( check(x,y+2) && state[x][y+2]==initial ){ q.push(make_pair(x,y+2)); state[x][y+2]=waiting; par[x][y+2].first=p.first; par[x][y+2].second=p.second; dis[x][y+2]=dis[par[x][y+2].first][par[x][y+2].second] + 1; } if( check(x+2,y+1) && state[x+2][y+1]==initial ){ q.push(make_pair(x+2,y+1)); state[x+2][y+1]=waiting; par[x+2][y+1].first=p.first; par[x+2][y+1].second=p.second; dis[x+2][y+1]=dis[par[x+2][y+1].first][par[x+2][y+1].second] + 1; } if( check(x+2,y-1) && state[x+2][y-1]==initial ){ q.push(make_pair(x+2,y-1)); state[x+2][y-1]=waiting; par[x+2][y-1].first=p.first; par[x+2][y-1].second=p.second; dis[x+2][y-1]=dis[par[x+2][y-1].first][par[x+2][y-1].second] + 1; } if( check(x,y+2) && state[x][y-2]==initial ){ q.push(make_pair(x,y-2)); state[x][y-2]=waiting; par[x][y-2].first=p.first; par[x][y-2].second=p.second; dis[x][y-2]=dis[par[x][y-2].first][par[x][y-2].second] + 1; } } } int main() { int a,b,c,d; // n number of nodes and m number of edges cin>>n>>a>>b>>c>>d; for(int i=0;i<=n-1;i++){ for(int j=0;j<=n-1;j++){ par[i][j].first=-1; par[i][j].second=-1; state[i][j]=initial; dis[i][j]=infinity; } } bfs(a,b); if(dis[c][d]!=infinity){ cout<d) s.push("LL"); if(p1==c && p2>d) s.push("L"); if(p1>c && p2>d) s.push("UL"); if(p1>c && p2