मान लीजिए, हमें m x n आयामों का एक ग्रिड दिया गया है। एक ऑब्जेक्ट सेल (ix, iy) पर रखा गया है और हमें ऑब्जेक्ट को शुरुआती स्थिति (sx, sy) से स्कैन करके ढूंढना है। स्कैनिंग एल्गोरिदम ग्रिड की iवीं पंक्ति और 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))
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#includeusing 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