Kiểm tra vua có bị chiếu hết khi có N mã trên bàn cờ vô hạn (C++)

Khái niệm

Cho bàn cờ vô hạn, N mã (knight) tại các tọa độ cho trước và tọa độ vua. Xác định xem vua có bị chiếu hết (không thể di chuyển hợp lệ) hay không.

Ví dụ 1: Mã: {{2,1},{1,3},{3,6},{5,5},{6,1},{7,3}}, Vua: {4,3} → Kết quả: Yes (chiếu hết).

Ví dụ 2: Mã: {{1,1}}, Vua: {3,4} → Kết quả: No (vua còn nước đi).

Phương pháp

Mã di chuyển theo hình chữ L (8 hướng). Dùng hash map (map<pair<int,int>, int>) đánh dấu tất cả ô mà mã có thể tấn công (kể cả vị trí hiện tại của mã). Sau đó kiểm tra 8 ô lân cận của vua: nếu tất cả đều bị đánh dấu → vua không có nước đi hợp lệ → chiếu hết.

Ví dụ (C++)

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

bool checkCheckMate1(pair<int, int> a1[], int n1, int kx1, int ky1){
    map<pair<int, int>, int> mpp1;
    for (int i = 0; i < n1; i++) {
        int x = a1[i].first, y = a1[i].second;
        mpp1[{x, y}] = 1;
        mpp1[{x-2, y+1}] = 1; mpp1[{x-2, y-1}] = 1;
        mpp1[{x+1, y+2}] = 1; mpp1[{x+1, y-2}] = 1;
        mpp1[{x-1, y+2}] = 1; mpp1[{x+2, y+1}] = 1;
        mpp1[{x+2, y-1}] = 1; mpp1[{x-1, y-2}] = 1;
    }
    for (int i = -1; i < 2; i++) {
        for (int j = -1; j < 2; j++) {
            int nx = kx1 + i, ny = ky1 + j;
            if (i != 0 && j != 0) {
                if (!mpp1[{nx, ny}]) return true; // Vua còn nước đi
            }
        }
    }
    return false; // Chiếu hết
}

int main(){
    pair<int, int> a1[] = { {2,1}, {1,3}, {3,6}, {5,5}, {6,1}, {7,3} };
    int n1 = sizeof(a1) / sizeof(a1[0]);
    int x = 4, y = 3;
    if (checkCheckMate1(a1, n1, x, y)) cout << "Not Checkmate!";
    else cout << "Yes its checkmate!";
    return 0;
}

Đầu ra

Yes its checkmate!