Advertisement
Guest User

Untitled

a guest
Sep 21st, 2019
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.09 KB | None | 0 0
  1.  
  2. class Solution {
  3.  
  4. public:
  5. map<pair<int,int>,int> mp;
  6. int minKnightMoves(int x, int y) {
  7. for(int i=-310;i<310;i++){
  8. for(int j=-310;j<310;j++){
  9. mp[make_pair(i,j)]++;
  10. }
  11. }
  12. return dp(0 ,0,x,y,0);
  13.  
  14.  
  15.  
  16. }
  17. int dp(int i,int j,int x,int y,int n){
  18. if(abs(i)>300 || abs(j)>300){
  19. return 100000;
  20. }
  21. if(i==0 && j==x){
  22. return n;
  23. }
  24. int a=100000;
  25.  
  26. if((abs(i+2)<=300 && abs(j+1)<=300)){
  27. if(mp[make_pair(i+2,j+1)]==1 ){
  28.  
  29. int p=dp(i+2,j+1,x,y,n+1);
  30. mp[make_pair(i+2,j+1)]=p;
  31. a=min(a,p);
  32.  
  33.  
  34. }else{
  35. a=min(a,mp[make_pair(i+2,j+1)]);
  36. }
  37. }
  38.  
  39.  
  40.  
  41.  
  42. if(abs(i+2)<=300 && abs(j-1)<=300){
  43. if( mp[make_pair(i+2,j-1)]==1){
  44. int p=dp(i+2,j-1,x,y,n+1);
  45. mp[make_pair(i+2,j-1)]=p;
  46. a=min(a, p);
  47. }else{
  48. a=min(a,mp[make_pair(i+2,j-1)]);
  49. }
  50. }
  51.  
  52. if(abs(i-2)<=300 && abs(j+1)<=300){
  53. if( mp[make_pair(i-2,j+1)]==1){
  54. int p=dp(i-2,j+1,x,y,n+1);
  55. mp[make_pair(i-2,j+1)]=p;
  56. a=min(a, p);
  57. }else{
  58. a=min(a, mp[make_pair(i-2,j+1)]);
  59. }
  60. }
  61.  
  62.  
  63.  
  64. if(abs(i-2)<=300 && abs(j-1)<=300){
  65. if( mp[make_pair(i-2,j-1)]==1){
  66. int p=dp(i-2,j-1,x,y,n+1);
  67. mp[make_pair(i-2,j-1)]=p;
  68. a=min(a, p);
  69. }else{
  70. a=min(a,mp[make_pair(i-2,j-1)]);
  71. }
  72. }
  73.  
  74.  
  75. if(abs(i+1)<=300 && abs(j+2)<=300){
  76. if( mp[make_pair(i+1,j+2)]==1){
  77. int p=dp(i+1,j+2,x,y,n+1);
  78. mp[make_pair(i+1,j+2)]=p;
  79. a=min(a, p);
  80. }else{
  81. a=min(a, mp[make_pair(i+1,j+2)]);
  82. }
  83. }
  84.  
  85.  
  86. if(abs(i+1)<=300 && abs(j-2)<=300){
  87. if( mp[make_pair(i+1,j-2)]==1){
  88. int p=dp(i+1,j-2,x,y,n+1);
  89. mp[make_pair(i+1,j-2)]=p;
  90. a=min(a, p);
  91. }else{
  92. a=min(a, dp(i+1,j-2,x,y,n+1));
  93. }
  94. }
  95.  
  96.  
  97. if(abs(i-1)<=300 && abs(j-2)<=300){
  98. if( mp[make_pair(i-1,j-2)]==1){
  99. int p=dp(i-1,j-2,x,y,n+1);
  100. mp[make_pair(i-1,j-2)]=p;
  101. a=min(a, p);
  102. }else{
  103. a=min(a,mp[make_pair(i-1,j-2)]);
  104. }
  105. }
  106.  
  107.  
  108. if(abs(i-1)<=300 && abs(j+2)){
  109. if( mp[make_pair(i-1,j+2)]==1){
  110. int p= dp(i-1,j+2,x,y,n+1);
  111. mp[make_pair(i-1,j+2)]=p;
  112. a=min(a,p);
  113. }else{
  114. a=min(a, mp[make_pair(i-1,j+2)]);
  115. }
  116. }
  117.  
  118.  
  119.  
  120.  
  121. return a;
  122. }
  123. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement