Kiểm tra lưới 2 hàng có thể đi từ (0,0) đến (1,n-1) bằng C++

Mô tả bài toán

Lưới 2 hàng, n cột. Ô '#' chặn, '.' trống. Robot ở (0,0) muốn đến (1,n-1), có thể đi ô liền kề (8 hướng). Kiểm tra có đường đi không.

Ví dụ

n=4, grid={".##.", "...."} → Possible.

Thuật toán

Nếu có cột nào cả hai hàng đều là '#' thì chặn đường. Ngược lại luôn có đường (vì có thể đi chéo).

Code C++

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

void solve(int n, vector grid) {
    bool ok = true;
    for (int i = 0; i < n; i++) {
        if (grid[0][i] == '#' && grid[1][i] == '#') {
            ok = false;
            break;
        }
    }
    cout << (ok ? "Possible." : "Not Possible.");
}

int main() {
    int n = 4;
    vector grid = {".##.", "...."};
    solve(n, grid);
    return 0;
}

Đầu vào / Đầu ra

Input: 4, {".##.", "...."}

Output: Possible.