数据结构
网络
关系数据库管理系统 (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 次查看
