Đếm số bước di chuyển có thể trong lưới theo hướng cho trước trong C++

Cho hai biến n và m đại diện cho lưới kích thước n x m và điểm bắt đầu (x, y). Cũng cho một danh sách các bước di chuyển moves (ví dụ: (1,1), (2,2)...). Mỗi cặp biểu thị số bước trên trục x, y. Mục tiêu: tìm tổng số bước có thể thực hiện trong lưới mà không vượt biên [1,n] x [1,m].

Ví dụ: n=5, m=4, vị trí (2,2), bước (1,-1). Lần 1: (3,1), lần 2: (4,-1) → vượt biên.

Ví dụ

Đầu vào − A=3, B=4, x=1, y=1; moves = {1,1}, {0,-1}

Đầu ra − 4

Giải thích:

Chọn {1,1}: (1,1)→(2,2)→(3,3) = 3 bước
Chọn {0,-1}: (3,3)→(3,2)→(3,1) = 2 bước
Tổng 4 bước (tính từ đầu)

Đầu vào − A=4, B=4, x=2, y=2; moves = {2,1}, {-2,-3}

Đầu ra − 1

Giải thích:

Chọn {2,1}: (2,2)→(4,3) = 1 bước
Chọn {-2,-3}: (4,3)→(2,0) vượt biên
Tổng 1 bước

Phương pháp giải

Tạo vector chứa các cặp bước pair. Từ điểm (x,y), chọn từng bước và tính số bước tối đa có thể đi trong mỗi hướng. Số bước cho phép là min của hai hướng.

• Hàm possible(int x, int temp_x, int A) tính số bước tối đa trên một trục:
  • Nếu temp_x == 0 → trả về INT_MAX.
  • Nếu temp_x > 0 → |A - x| / temp_x.
  • Nếu temp_x < 0 → |x - 1| / |temp_x|.
• Hàm possible_moves(...):
  • Khởi tạo count = 0.
  • Duyệt qua vector bước:
    • Lấy temp_x, temp_y.
    • check = min(possible(x, temp_x, A), possible(y, temp_y, B)).
    • count += check.
    • Cập nhật x += check * temp_x, y += check * temp_y.
  • Trả về count.

Ví dụ code

#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 += check;
        x += check * temp_x;
        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

Count of possible moves in the given direction in a grid are: 3