Chương trình C++ tìm số bước tối thiểu di chuyển từ (0,0) đến (x,y)

Robot tại (0,0) muốn đến (x,y). Mỗi bước: lên, xuống, trái, phải, hoặc đứng yên. Tìm số bước tối thiểu.

Ví dụ

Với x=3, y=4, đầu ra 7.

Giải thuật

Khoảng cách Manhattan = |x|+|y|. Nhưng có thể đứng yên. Công thức: x + y + min(|x-y|, |x-y+1|, |x-y-1|). (Giả sử x,y ≥ 0).

Mã C++

#include <bits/stdc++.h>
using namespace std;

int solve(int x, int y) {
    return x + y + min(abs(x - y), min(abs(x - y + 1), abs(x - y - 1)));
}

int main() {
    int x = 3, y = 4;
    cout << solve(x, y) << endl;
}

Đầu vào / Đầu ra

Input: 3, 4
Output: 7