สมมติว่าเราได้รับตารางขนาด 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
