Kiểm tra châu chấu có nhảy đến đích được không bằng C++

Mô tả bài toán

Chuỗi S chứa '.', '#', 'G', 'T'. 'G' vị trí bắt đầu, 'T' đích, '#' chướng ngại vật. Châu chấu nhảy đúng k ô mỗi lần. Kiểm tra có thể đến đích không.

Ví dụ

S="#G#T#", k=2 → G ở 1, T ở 3, khoảng cách 2, không có chướng ngại vật giữa → True.

Thuật toán

Tìm vị trí G (x) và T (y). Đảm bảo x

Code C++

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

bool solve(string S, int k) {
    int x = S.find('G');
    int y = S.find('T');
    if (x > y) swap(x, y);
    for (int i = x; i < y; i += k) {
        if (S[i] == '#') return false;
    }
    return (y - x) % k == 0;
}

int main() {
    string S = "#G#T#";
    int k = 2;
    cout << solve(S, k) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: "#G#T#", 2

Output: 1 (true)