Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++의 그리드에서 주어진 방향으로 가능한 이동 계산

<시간/>

우리는 n x m 크기의 격자와 시작할 초기점 x,y를 나타내는 두 개의 변수 n과 m입니다.

또한 이동( (1,1), (2,2) ) 등으로 그리드 내부를 횡단하는 데 사용할 수 있는 단계/이동 쌍이 제공됩니다. 각 이동 쌍은 x,y 축에서 취한 단계 단위를 나타냅니다. 목표는 경계 [1,n] X [1,m] 내에서 그리드 내부를 횡단하는 데 수행할 수 있는 총 단계를 찾는 것입니다. n이 5이고 m이 4이고 현재 위치가 2,2이고 선택된 단계가 ( 1,-1) 그런 다음 이 단계를 한 번 수행하면 (3,1)이 되고, 이 단계를 다시 수행하면 (4,-1)이 됩니다. 이는 -1이 범위를 벗어났기 때문에 유효하지 않습니다.

C++의 그리드에서 주어진 방향으로 가능한 이동 계산

예를 들어 이해하자

입력 - 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

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

이 접근 방식에서 우리는 pair로 단계를 나타내는 벡터를 생성할 것입니다. x,y 지점에서 횡단을 시작합니다. 벡터에서 한 단계를 선택하고 양방향(x축 및 y축)에서 취한 값의 최소값을 선택합니다. 선택한 최소값은 더 많은 이동을 허용합니다. 특정 방향으로 이동하기 위해 현재 위치 x(또는 y)가> n(또는 m)이면 n(또는 m)에 도달하기 위한 이동 횟수는 ( n - 현재 위치 )/x입니다. 이보다 작으면 1에 도달하기 위한 이동 수는 ( 현재 위치 - 1 )/x입니다.

  • AXB 그리드를 나타내는 변수 A,B와 시작점에 대한 x,y 변수를 사용합니다.

  • 정수 쌍을 포함하는 벡터를 이동으로 사용합니다( vector > ).

  • 함수 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 루프를 사용하여 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