Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- map<pair<int,int>,int> mp;
- int minKnightMoves(int x, int y) {
- for(int i=-310;i<310;i++){
- for(int j=-310;j<310;j++){
- mp[make_pair(i,j)]++;
- }
- }
- return dp(0 ,0,x,y,0);
- }
- int dp(int i,int j,int x,int y,int n){
- if(abs(i)>300 || abs(j)>300){
- return 100000;
- }
- if(i==0 && j==x){
- return n;
- }
- int a=100000;
- if((abs(i+2)<=300 && abs(j+1)<=300)){
- if(mp[make_pair(i+2,j+1)]==1 ){
- int p=dp(i+2,j+1,x,y,n+1);
- mp[make_pair(i+2,j+1)]=p;
- a=min(a,p);
- }else{
- a=min(a,mp[make_pair(i+2,j+1)]);
- }
- }
- if(abs(i+2)<=300 && abs(j-1)<=300){
- if( mp[make_pair(i+2,j-1)]==1){
- int p=dp(i+2,j-1,x,y,n+1);
- mp[make_pair(i+2,j-1)]=p;
- a=min(a, p);
- }else{
- a=min(a,mp[make_pair(i+2,j-1)]);
- }
- }
- if(abs(i-2)<=300 && abs(j+1)<=300){
- if( mp[make_pair(i-2,j+1)]==1){
- int p=dp(i-2,j+1,x,y,n+1);
- mp[make_pair(i-2,j+1)]=p;
- a=min(a, p);
- }else{
- a=min(a, mp[make_pair(i-2,j+1)]);
- }
- }
- if(abs(i-2)<=300 && abs(j-1)<=300){
- if( mp[make_pair(i-2,j-1)]==1){
- int p=dp(i-2,j-1,x,y,n+1);
- mp[make_pair(i-2,j-1)]=p;
- a=min(a, p);
- }else{
- a=min(a,mp[make_pair(i-2,j-1)]);
- }
- }
- if(abs(i+1)<=300 && abs(j+2)<=300){
- if( mp[make_pair(i+1,j+2)]==1){
- int p=dp(i+1,j+2,x,y,n+1);
- mp[make_pair(i+1,j+2)]=p;
- a=min(a, p);
- }else{
- a=min(a, mp[make_pair(i+1,j+2)]);
- }
- }
- if(abs(i+1)<=300 && abs(j-2)<=300){
- if( mp[make_pair(i+1,j-2)]==1){
- int p=dp(i+1,j-2,x,y,n+1);
- mp[make_pair(i+1,j-2)]=p;
- a=min(a, p);
- }else{
- a=min(a, dp(i+1,j-2,x,y,n+1));
- }
- }
- if(abs(i-1)<=300 && abs(j-2)<=300){
- if( mp[make_pair(i-1,j-2)]==1){
- int p=dp(i-1,j-2,x,y,n+1);
- mp[make_pair(i-1,j-2)]=p;
- a=min(a, p);
- }else{
- a=min(a,mp[make_pair(i-1,j-2)]);
- }
- }
- if(abs(i-1)<=300 && abs(j+2)){
- if( mp[make_pair(i-1,j+2)]==1){
- int p= dp(i-1,j+2,x,y,n+1);
- mp[make_pair(i-1,j+2)]=p;
- a=min(a,p);
- }else{
- a=min(a, mp[make_pair(i-1,j+2)]);
- }
- }
- return a;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement