ধরুন, আমাদেরকে m x n মাত্রার একটি গ্রিড দেওয়া হয়েছে। একটি বস্তুকে কক্ষে (ix, iy) স্থাপন করা হয় এবং আমাদের একটি প্রারম্ভিক অবস্থান (sx, sy) থেকে স্ক্যান করা বস্তুটি খুঁজে বের করতে হবে। স্ক্যানিং অ্যালগরিদম গ্রিডের ith সারি এবং j-ম কলাম স্ক্যান করে যদি এটি গ্রিডের ঘরে (i, j) অবস্থিত থাকে। যদি এটি বস্তুটি খুঁজে পায়, স্ক্যানিং বন্ধ হয়ে যায়; যদি না হয়, স্ক্যানিং পয়েন্টারটি অবস্থানে (i + 1, j + 1) ঘরে চলে যায় এবং তারপরে একইভাবে স্ক্যান করে। আইটেম পাওয়া না হওয়া পর্যন্ত এটি চলতে থাকে। অবস্থানের পরিপ্রেক্ষিতে, বস্তুটি খুঁজতে অ্যালগরিদমকে কতগুলি স্ক্যান করতে হবে তা আমাদের খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুট n =20, m =20, sx =3, sy =2, ix =12, iy =4 এর মত হয়, তাহলে আউটপুট হবে 2।
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
t1 := (if sx <= ix, then ix - sx, otherwise 2 * n - ix - sx) t2 := (if sy <= iy, then iy - sy, otherwise 2 * m - iy - sy) print(minimum of (t1, t2))
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
#define N 100
void solve(int n, int m, int sx, int sy, int ix, int iy) {
int t1 = (sx <= ix ? ix - sx : 2 * n - ix - sx);
int t2 = (sy <= iy ? iy - sy : 2 * m - iy - sy);
cout<< min(t1, t2);
}
int main() {
int n = 20, m = 20, sx = 3, sy = 2 , ix = 12, iy = 4;
solve(n, m, sx, sy, ix, iy);
return 0;
} ইনপুট
20, 20, 3, 2 , 12, 4
আউটপুট
2
