ধরুন আমাদের কাছে -ইনফিনিটি থেকে +ইনফিনিটি পর্যন্ত স্থানাঙ্ক সহ একটি অসীম চেসবোর্ড আছে, এবং আমাদের বর্গাকার [0, 0]-এ একটি নাইট আছে। একটি নাইটের 8টি সম্ভাব্য চাল রয়েছে যা এটি করতে পারে, যেমনটি নীচে দেখানো হয়েছে। প্রতিটি চাল একটি মূল দিক থেকে দুটি বর্গক্ষেত্র, তারপর একটি অর্থোগোনাল দিকে একটি বর্গক্ষেত্র।
নাইটটিকে বর্গক্ষেত্রে [x, y] সরানোর জন্য আমাদের প্রয়োজনীয় ন্যূনতম সংখ্যক ধাপ খুঁজে বের করতে হবে। এটা নিশ্চিত যে উত্তর আছে।
সুতরাং ইনপুট যদি x =5 এবং y =5 এর মত হয়, তাহলে আউটপুট হবে 4। এটি হবে [0,0] → [2,1] → [4,2] → [3,4] → [ 5,5]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি মানচিত্র m
সংজ্ঞায়িত করুন -
সমাধান() নামক একটি পদ্ধতি নির্ধারণ করুন, এটি x এবং y
লাগবে -
যদি x + y =0 হয়, তাহলে 0 ফেরত দিন, যদি x + y =2 হয়, তাহলে 2 ফেরত দিন
-
(x, y)
ব্যবহার করে একটি জোড়া তাপমাত্রা তৈরি করুন -
যদি m এর জোড়া temp থাকে, তাহলে m[temp]
ফেরত দিন -
ফিরুন m[temp] :=সমাধানের মিনিট(|x - 1|, |y - 2|)), [সমাধান(|x - 2|, |y - 1|)) + 1]
-
মূল পদ্ধতি থেকে, কল solve(|x|, |y|), এবং এর মান ফেরত দিন
উদাহরণ (C++)
আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
map < pair <int, int>, int > dp;
int solve(int x, int y){
if(x + y == 0) return 0;
if (x + y == 2) return 2;
pair <int, int> temp({x, y});
if(dp.count(temp)) return dp[temp];
return dp[temp] = min(solve(abs(x - 1), abs(y - 2)), solve(abs(x - 2), abs(y - 1))) + 1;
}
int minKnightMoves(int x, int y) {
return solve(abs(x), abs(y));
}
};
main(){
Solution ob;
cout << (ob.minKnightMoves(5, 5));
} ইনপুট
5 5
আউটপুট
4
