#include #include #include using namespace std; const int N = 2.5e5 + 5; #define MOD 1000000007 #define lli long long int #define ulli unsigned long long int #define fr first #define sc second #define INF 1e9 #define L_INF 1e18 #define p_b push_back #define m_p make_pair #define plli pair #define pii pair map mp; pair< int,pair > grid[201][201]; int n; string fun(int x1,int y1,int n_x,int n_y){ string ret; if(n_x==x1 && n_y-2==y1){ ret="L"; } if(n_x==x1 && n_y+2==y1){ ret="R"; } if(n_x-2==x1 && n_y-1==y1){ ret="UL"; } if(n_x-2==x1 && n_y+1==y1){ ret="UR"; } if(n_x+2==x1 && n_y-1==y1){ ret="LL"; } if(n_x+2==x1 && n_y+1==y1){ ret="LR"; } return ret; } void bfs(int x,int y){ queue > q; q.push(m_p(x,y)); grid[x][y].fr=0; grid[x][y].sc.fr=-1; grid[x][y].sc.sc=-1; while(!q.empty()){ pair p1=q.front(); q.pop(); int x1=p1.fr; int y1=p1.sc; if(x1-2>=0 && y1-1>=0 && grid[x1-2][y1-1].fr==grid[x1][y1].fr+1){ string s1=fun(x1-2,y1-1,x1,y1); string s2=fun(x1-2,y1-1,grid[x1-2][y1-1].sc.fr,grid[x1-2][y1-1].sc.sc); if(mp[s1]>mp[s2]){ grid[x1-2][y1-1].fr=grid[x1][y1].fr+1; grid[x1-2][y1-1].sc.fr=x1; grid[x1-2][y1-1].sc.sc=y1; q.push(m_p(x1-2,y1-1)); } } if(x1-2>=0 && y1+1mp[s2]){ grid[x1-2][y1+1].fr=grid[x1][y1].fr+1; grid[x1-2][y1+1].sc.fr=x1; grid[x1-2][y1+1].sc.sc=y1; q.push(m_p(x1-2,y1+1)); } } if(x1+2=0 && grid[x1+2][y1-1].fr==grid[x1][y1].fr+1){ string s1=fun(x1+2,y1-1,x1,y1); string s2=fun(x1+2,y1-1,grid[x1+2][y1-1].sc.fr,grid[x1+2][y1-1].sc.sc); if(mp[s1]>mp[s2]){ grid[x1+2][y1-1].fr=grid[x1][y1].fr+1; grid[x1+2][y1-1].sc.fr=x1; grid[x1+2][y1-1].sc.sc=y1; q.push(m_p(x1+2,y1-1)); } } if(x1+2mp[s2]){ grid[x1+2][y1+1].fr=grid[x1][y1].fr+1; grid[x1+2][y1+1].sc.fr=x1; grid[x1+2][y1+1].sc.sc=y1; q.push(m_p(x1+2,y1+1)); } } if(y1+2mp[s2]){ grid[x1][y1+2].fr=grid[x1][y1].fr+1; grid[x1][y1+2].sc.fr=x1; grid[x1][y1+2].sc.sc=y1; q.push(m_p(x1,y1+2)); } } if(y1-2>=0 && grid[x1][y1-2].fr==grid[x1][y1].fr+1){ string s1=fun(x1,y1-2,x1,y1); string s2=fun(x1,y1-2,grid[x1][y1-2].sc.fr,grid[x1][y1-2].sc.sc); if(mp[s1]>mp[s2]){ grid[x1][y1-2].fr=grid[x1][y1].fr+1; grid[x1][y1-2].sc.fr=x1; grid[x1][y1-2].sc.sc=y1; q.push(m_p(x1,y1-2)); } } if(x1-2>=0 && y1-1>=0 && grid[x1-2][y1-1].fr>grid[x1][y1].fr+1){ grid[x1-2][y1-1].fr=grid[x1][y1].fr+1; grid[x1-2][y1-1].sc.fr=x1; grid[x1-2][y1-1].sc.sc=y1; q.push(m_p(x1-2,y1-1)); } if(x1-2>=0 && y1+1grid[x1][y1].fr+1){ grid[x1-2][y1+1].fr=grid[x1][y1].fr+1; grid[x1-2][y1+1].sc.fr=x1; grid[x1-2][y1+1].sc.sc=y1; q.push(m_p(x1-2,y1+1)); } if(x1+2=0 && grid[x1+2][y1-1].fr>grid[x1][y1].fr+1){ grid[x1+2][y1-1].fr=grid[x1][y1].fr+1; grid[x1+2][y1-1].sc.fr=x1; grid[x1+2][y1-1].sc.sc=y1; q.push(m_p(x1+2,y1-1)); } if(x1+2grid[x1][y1].fr+1){ grid[x1+2][y1+1].fr=grid[x1][y1].fr+1; grid[x1+2][y1+1].sc.fr=x1; grid[x1+2][y1+1].sc.sc=y1; q.push(m_p(x1+2,y1+1)); } if(y1+2grid[x1][y1].fr+1){ grid[x1][y1+2].fr=grid[x1][y1].fr+1; grid[x1][y1+2].sc.fr=x1; grid[x1][y1+2].sc.sc=y1; q.push(m_p(x1,y1+2)); } if(y1-2>=0 && grid[x1][y1-2].fr>grid[x1][y1].fr+1){ grid[x1][y1-2].fr=grid[x1][y1].fr+1; grid[x1][y1-2].sc.fr=x1; grid[x1][y1-2].sc.sc=y1; q.push(m_p(x1,y1-2)); } } } int main(){ mp.insert(m_p("R",1)); mp.insert(m_p("UR",2)); mp.insert(m_p("UL",3)); mp.insert(m_p("L",4)); mp.insert(m_p("LL",5)); mp.insert(m_p("LR",6)); for(int i=0;i<201;i++){ for(int j=0;j<201;j++){ grid[i][j].fr=1000000000; } } cin>>n; int s_x,s_y,e_x,e_y; cin>>s_x>>s_y>>e_x>>e_y; bfs(e_x,e_y); /*for(int i=0;i ar; int x1=s_x,y1=s_y; while(x1!=-1 ){ int n_x=grid[x1][y1].sc.fr; int n_y=grid[x1][y1].sc.sc; //cout<