Chúng tôi là hai biến n và m đại diện cho một lưới kích thước n x m và điểm ban đầu x, y để bắt đầu.
Cũng cho các cặp bước / bước di chuyển có thể được thực hiện để đi qua bên trong lưới như các bước di chuyển ((1,1), (2,2)), v.v. Mỗi cặp bước di chuyển đại diện cho đơn vị bước được thực hiện trong trục x, y. Mục tiêu là tìm tổng số bước có thể được thực hiện để đi qua bên trong lưới trong ranh giới [1, n] X [1, m] Nếu n là 5 và m là 4 và vị trí hiện tại là 2,2 và bước được chọn là ( 1, -1) sau đó thực hiện bước này một lần sẽ dẫn đến (3,1), thực hiện lại bước này sẽ dẫn đến (4, -1) không hợp lệ vì -1 đã hết ràng buộc.
Hãy cho chúng tôi hiểu với các ví dụ
Đầu vào - A =3, B =4, x =1, y =1; di chuyển ={1, 1}, {0, -1}
Đầu ra - Số lượt di chuyển có thể có theo hướng đã cho trong lưới là - 4
Giải thích -
Choosing move {1,1} = → (2,2) → (3,3) - 3 steps
Choosing move {0,-1} = → (3,2) → (3,1) - 2 steps
Total 4 steps. Đầu vào - A =4, B =4, x =2, y =2; di chuyển ={2, 1}, {-2, -3}
Đầu ra - Số lượt di chuyển có thể có theo hướng đã cho trong lưới là - 1
Giải thích
Choosing move {2,1} = → (4,3) - 1 step1
Choosing move {-2,-3} = → (2,0) X out of bound
Total 1 step Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong cách tiếp cận này, chúng ta sẽ tạo một vector biểu diễn các bước dưới dạng cặp
-
Lấy các biến A, B để đại diện cho lưới AXB và x, y cho điểm bắt đầu.
-
Lấy một vectơ chứa các cặp số nguyên làm di chuyển (vectơ
>). -
Hàm could_moves (int x, int y, int A, int B, vector
> move, int size) nhận tất cả các biến và di chuyển và trả về số lần di chuyển có thể có theo hướng đã cho trong một lưới. -
Hàm có thể (int x, int temp_x, int A) nhận vị trí hiện tại của tọa độ là x, giá trị tọa độ tương ứng khi di chuyển là temp_x và giới hạn của Grid cho tọa độ đó là A.
-
Bây giờ nếu temp_x là 0, hãy trả về INT_MAX để tạo giá trị trả về là lớn nhất.
-
Nếu temp_x> 0 thì các bước di chuyển đến A sẽ là | A-x | / temp_x
-
Khác để di chuyển về phía 1 nước đi sẽ là | x-1 | / temp_x.
-
Trả lại các bước di chuyển được tính toán tương ứng.
-
Bên trong could_moves (), lấy số lượng ban đầu là 0.
-
Vectơ di chuyển bằng vòng lặp for từ i =0 đến i
-
Trích xuất tọa độ từ cặp di chuyển hiện tại dưới dạng temp_x =move [i] .first và temp_y =move [i] .second.
-
Thực hiện các kiểm tra biến đổi ở mức tối thiểu các lần di chuyển có thể sử dụng hàm ().
-
Giá trị tối thiểu trong séc sẽ được thêm vào để tính cho tổng số bước.
-
Bây giờ chúng tôi đã chọn séc, hãy cập nhật x và y bằng séc.
-
Cuối cùng, chúng tôi sẽ nhận được tổng số các bước di chuyển có thể có theo hướng nhất định trong một lưới
-
Kết quả là số lượt trả lại.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of possible moves in the given direction in a grid are: 3