資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學在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
解釋 −
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; moves = { 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下面程式中使用的方法如下：
在這種方法中，我們將建立一個向量來表示步數，表示為pair<int,int>。從點x,y開始遍歷。從向量中選擇一步，並選擇兩個方向（x軸和y軸）上所取值的最小值。選擇的最小值將允許更多移動。為了朝特定方向移動，如果當前位置x（或y）> n（或m），則到達n（或m）的移動次數為(n - 當前位置)/x。如果小於，則到達1的移動次數為(當前位置 - 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()內部，將初始計數設為0。
使用for迴圈從i=0到i<size遍歷向量。
從當前移動對中提取座標，作為temp_x=move[i].first和temp_y=move[i].second。
使用函式possible()獲取可能移動次數的最小值作為變數checks。
check中的最小值將新增到計數中以計算總步數。
現在我們選擇了check，透過check更新x和y。
最後，我們將得到網格中給定方向上可能移動的總數。
返回count作為結果。
示例
#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
222 次檢視
