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

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

นอกจากนี้ยังมีคู่ของขั้นตอน/การเคลื่อนที่ที่สามารถนำไปใช้เพื่อเดินทางภายในกริด เช่น moves ( (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; moves = { 1, 1 }, { 0, -1 }

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

คำอธิบาย −

เลือกการเคลื่อนที่ {1,1} = → (2,2) → (3,3) - 3 ขั้นตอน
เลือกการเคลื่อนที่ {0,-1} = → (3,2) → (3,1) - 2 ขั้นตอน
รวม 4 ขั้นตอน

อินพุต − A = 4, B = 4, x =2, y = 2; moves = { 2, 1 }, { -2, -3 }

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

คำอธิบาย

เลือกการเคลื่อนที่ {2,1} = → (4,3) - 1 ขั้นตอน
เลือกการเคลื่อนที่ {-2,-3} = → (2,0) X นอกขอบเขต
รวม 1 ขั้นตอน

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

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

• รับตัวแปร A,B แทนกริด AXB และ x,y สำหรับจุดเริ่มต้น
• รับเวกเตอร์ที่มีคู่จำนวนเต็มเป็นการเคลื่อนที่ (vector <pair<int, int> > )
• ฟังก์ชัน possible_moves(int x, int y, int A, int B, vector<pair<int, int>> move, int size) รับตัวแปรทั้งหมดและการเคลื่อนที่ คืนจำนวนการเคลื่อนที่ที่เป็นไปได้
• ฟังก์ชัน possible(int x, int temp_x, int A) รับตำแหน่งปัจจุบันของพิกัดเป็น x ค่าพิกัดที่สอดคล้องในการเคลื่อนที่เป็น temp_x และขอบเขตกริดสำหรับพิกัดนั้นเป็น A
• ถ้า temp_x เป็น 0 คืน INT_MAX เพื่อให้ค่าสูงสุด
• ถ้า temp_x > 0 ขั้นตอนเพื่อไปถึง A คือ | A-x |/temp_x
• มิฉะนั้น สำหรับเคลื่อนที่ไป 1 ขั้นตอนจะเป็น | x-1 |/temp_x
• คืนค่าขั้นตอนที่คำนวณได้
• ใน possible_moves() กำหนด count เริ่มต้นเป็น 0
• วนลูปเวกเตอร์จาก i=0 ถึง i<size
• ดึงพิกัดจากคู่การเคลื่อนที่ปัจจุบันเป็น temp_x=move[i].first และ temp_y=move[i].second
• ตัวแปร checks เป็นค่าต่ำสุดของขั้นตอนที่เป็นไปได้จากฟังก์ชัน possible()
• ค่าต่ำสุดใน check จะถูกบวกเข้า count สำหรับขั้นตอนรวม
• อัปเดต x และ y ด้วย check
• สุดท้ายได้จำนวนการเคลื่อนที่ทั้งหมด คืน count

ตัวอย่างโค้ด C++

#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