นับการเคลื่อนไหวที่เป็นไปได้ในทิศทางที่กำหนดในตารางใน C++

เราเป็นสองตัวแปร n และ m แทนตารางขนาด n x m และจุดเริ่มต้น x,y ที่จะเริ่มต้น

นอกจากนี้ ยังมีขั้นตอน/การเคลื่อนไหวอีกคู่ที่สามารถเคลื่อนข้ามภายในตารางเป็นการเคลื่อนไหว ( (1,1), (2,2) ) เป็นต้น การเคลื่อนไหวแต่ละคู่แสดงถึงหน่วยของขั้นตอนที่ดำเนินการในแกน x,y เป้าหมายคือการหาขั้นตอนทั้งหมดที่สามารถใช้ในการสำรวจภายในเส้นตารางภายในขอบเขต [1,n] X [1,m] ถ้า n คือ 5 และ m คือ 4 และตำแหน่งปัจจุบันคือ 2,2 และขั้นตอนที่เลือกคือ ( 1,-1) จากนั้นทำตามขั้นตอนนี้ครั้งเดียวจะนำไปสู่ ​​(3,1) ทำตามขั้นตอนนี้อีกครั้งจะนำไปสู่ ​​(4,-1) ซึ่งไม่ถูกต้องเนื่องจาก -1 อยู่นอกขอบเขต

ให้เราเข้าใจด้วยตัวอย่าง

ป้อนข้อมูล − A =3, B =4, x =1, y =1; เคลื่อนที่ ={ 1, 1 }, { 0, -1 }

ผลผลิต − จำนวนการเคลื่อนที่ที่เป็นไปได้ในทิศทางที่กำหนดในตารางคือ − 4

คำอธิบาย −

Choosing move {1,1} = → (2,2) → (3,3) - 3 steps
Choosing move {0,-1} = → (3,2) → (3,1) - 2 steps
Total 4 steps.

ป้อนข้อมูล − A =4, B =4, x =2, y =2; เคลื่อนที่ ={ 2, 1 }, { -2, -3 }

ผลผลิต − จำนวนการเคลื่อนที่ที่เป็นไปได้ในทิศทางที่กำหนดในตารางคือ − 1

คำอธิบาย

Choosing move {2,1} = → (4,3) - 1 step1
Choosing move {-2,-3} = → (2,0) X out of bound
Total 1 step

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

ในแนวทางนี้ เราจะสร้างเวกเตอร์ที่แสดงขั้นตอนเป็นคู่ เริ่มข้ามจากจุด x,y เลือกขั้นตอนจากเวกเตอร์และเลือกค่าต่ำสุดที่ถ่ายในทั้งสองทิศทาง (แกน x และแกน y) ขั้นต่ำที่เลือกจะอนุญาตให้มีการเคลื่อนไหวมากขึ้น หากต้องการเคลื่อนที่ไปในทิศทางใดทิศทางหนึ่ง หากตำแหน่ง cur x ( หรือ y ) คือ> n (หรือ m) จำนวนการเคลื่อนที่ที่จะไปถึง n (หรือ m) จะเท่ากับ ( n - cur position )/x หากน้อยกว่านั้นจำนวนการเคลื่อนไหวที่จะไปถึง 1 คือ ( ตำแหน่ง cur - 1 )/x.

• นำตัวแปร A,B มาแทนตาราง AXB และ x,y สำหรับจุดเริ่มต้น

• หาเวกเตอร์ที่มีคู่จำนวนเต็มเป็นการเคลื่อนไหว (เวกเตอร์ > )

• ฟังก์ชัน possible_moves(int x, int y, int A, int B, vector> move, int size) รับตัวแปรทั้งหมดและย้ายและส่งกลับจำนวนการเคลื่อนที่ที่เป็นไปได้ในทิศทางที่กำหนดในตาราง

• ฟังก์ชันที่เป็นไปได้ (int x, int temp_x, int A) รับตำแหน่งพิกัดปัจจุบันเป็น x ค่าพิกัดที่สอดคล้องกันในการย้ายเป็น temp_x และขีดจำกัดของ Grid สำหรับพิกัดนั้นเป็น A

• ตอนนี้ถ้า temp_x เป็น 0 ให้คืนค่า INT_MAX เพื่อให้คืนค่าเป็นค่าสูงสุด

• หาก temp_x คือ> 0 แล้วเลื่อนไปถึง A จะเป็น | A-x |/temp_x

• อื่น ๆ สำหรับการย้ายไปยัง 1 ย้ายจะเป็น | x-1 |/temp_x.

• ส่งคืนการเคลื่อนไหวที่คำนวณได้ที่เกี่ยวข้อง

• ภายใน possible_moves() ให้นับเริ่มต้นเป็น 0

• เวกเตอร์การเคลื่อนที่โดยใช้ for loop จาก i=0 ถึง i

• แยกพิกัดจากคู่ของการเคลื่อนไหวปัจจุบันเป็น temp_x=move[i].first และ temp_y=move[i].second.

• ทำการตรวจสอบตัวแปรให้น้อยที่สุดเท่าที่จะเป็นไปได้โดยใช้ฟังก์ชันที่เป็นไปได้ ()

• ระบบจะเพิ่มมูลค่าขั้นต่ำในเช็คเพื่อนับจำนวนก้าวทั้งหมด

• ตอนนี้เราเลือกตรวจสอบแล้ว อัปเดต x และ y โดยกาเครื่องหมาย

• ในที่สุด เราก็จะได้จำนวนการเคลื่อนที่ที่เป็นไปได้ทั้งหมดในทิศทางที่กำหนดในตาราง

• ผลตอบแทนนับเป็นผลลัพธ์

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int possible(int x, int temp_x, int A){
   if(temp_x == 0){
      return INT_MAX;
   }
   if (temp_x > 0){
      return abs((A - x) / temp_x);
   }
   else{
      return abs((x - 1) / temp_x);
   }
}
int possible_moves(int x, int y, int A, int B, vector<pair<int, int>> move, int size){
   int count = 0;
   for (int i = 0; i < size; i++){
      int temp_x = move[i].first;
      int temp_y = move[i].second;
      int check = min(possible(x, temp_x, A), possible(y, temp_y, B));
      count = count + check;
      x = x + check * temp_x;
      y = y + check * temp_y;
   }
   return count;
}
int main(){
   int A = 3, B = 6, x = 3, y = 3;
   vector<pair<int, int> > move = {
      { 2, -1 },
      { 0, 1 },
      { 1, -2 }
   };
   int size = move.size();
   cout<<"Count of possible moves in the given direction in a grid are: "<<possible_moves(x, y, A, B, move, size);
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count of possible moves in the given direction in a grid are: 3