ধরুন আমাদের একটি অসীম চেসবোর্ড আছে যার কোঅরডিনেট -ইনফিনিটি থেকে +ইনফিনিটি, এবং [0, 0] স্কোয়ারে একটি নাইট আছে। নাইটের ৮টি সম্ভাব্য মুভ থাকে, যা নিচে দেখানো হলো। প্রতিটি মুভ কার্ডিনাল ডিরেকশনে দুটি স্কোয়ার, তারপর অর্থোগোনাল ডিরেকশনে একটি স্কোয়ার।
আমাদের [x, y] স্কোয়ারে নাইটটি পৌঁছাতে ন্যূনতম স্টেপ সংখ্যা খুঁজে বের করতে হবে। উত্তর অস্তিত্বের গ্যারান্টি দেওয়া আছে।
যেন ইনপুট x = 5 এবং y = 5, তবে আউটপুট হবে 4। পথটি হবে: [0,0] → [2,1] → [4,2] → [3,4] → [5,5]
সমাধান পদ্ধতি
- একটি ম্যাপ m ডিফাইন করুন
- solve() মেথড ডিফাইন করুন, যা x এবং y নেবে
- যদি x + y = 0, তবে 0 রিটার্ন করুন; যদি x + y = 2, তবে 2 রিটার্ন করুন
- (x, y) ব্যবহার করে একটি পেয়ার temp বানান
- যদি m-এ temp পেয়ারটি থাকে, তবে m[temp] রিটার্ন করুন
- m[temp] := min(solve(|x-1|, |y-2|), solve(|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)); } }; int main(){ Solution ob; cout << (ob.minKnightMoves(5, 5)); }ইনপুট
5 5
আউটপুট
4
