ตรวจสอบว่าเป็นไปได้หรือไม่ที่จะย้ายจากพิกัดที่กำหนดไปยังพิกัดที่ต้องการใน C++

สมมุติว่าเรามีสองพิกัด (sx, sy) และ (tx, ty) เราต้องตรวจสอบว่าเราสามารถย้ายจากจุดเริ่มต้นไปยังจุดสิ้นสุดได้หรือไม่ ในที่นี้ เราสามารถเคลื่อนที่ได้โดยใช้จุด (x, y) และแปลงเป็น (x, x+y) หรือ (x+y, y)

ดังนั้นหากอินพุตคือ (1, 1) และ (4,5) คำตอบจะเป็นจริง นั่นเป็นเพราะย้าย (1,1) ไปที่ (2,1) จากนั้น (3,1) แล้วก็ (4 ,1) แล้วก็ (4,5)

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ในขณะที่ tx> sx และ ty> sy ทำ −
  • ถ้า tx> ty แล้ว −
    • tx :=tx mod ty
  • มิฉะนั้น
    • ty :=ty mod tx
• ผลตอบแทน (จริงเมื่อ sx เหมือนกับ tx และ sy <=ty และ (ty - sy) mod tx เหมือนกับ 0) OR (sy เหมือนกับ ty AND x>=sx AND (tx - sx) mod ty คือ 0)

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
bool solve(int sx, int sy, int tx, int ty) {
   while(tx > sx && ty > sy){
      if(tx > ty){
         tx %= ty;
      }else ty %= tx;
   }
   return (sx == tx && sy <= ty && (ty - sy) % tx == 0) || (sy == ty && tx >= sx && (tx - sx) % ty == 0);
}
main(){
   cout << solve(1,1,4,5);
}

อินพุต

1, 1, 4, 5

ผลลัพธ์

1