ตรวจสอบว่าราชาเดินได้หรือไม่เมื่อมีหลังม้าบนกระดานหมากรุกใน C++

แนวคิด

กำหนดกระดานหมากรุกขนาดอันนิยต มี N ตัวม้า (Knight) และตำแหน่งของราชา (King) ต้องการตรวจสอบว่าราชาถูก "เช็กเมต" (Checkmate) หรือไม่ คือไม่สามารถเดินไปช่องใดๆ รอบๆ ได้ 8 ทิศทาง

ตัวอย่าง: - ม้า: {(2,1), (1,3), (3,6), (5,5), (6,1), (7,3)}, ราชา: (4,3) → Yes (เช็กเมต) - ม้า: {(1,1)}, ราชา: (3,4) → No (เดินได้)

วิธีการแก้ปัญหา

ม้าเดินแบบ "L" (2 ช่องแนวนอน 1 ช่องแนวตั้ง หรือ 2 ช่องแนวตั้ง 1 ช่องแนวนอน) มี 8 ทิศทาง สร้าง hash map บันทึกพิกัดทั้งหมดที่ม้าแต่ละตัวเดินถึงได้ รวมถึงตำแหน่งของม้าเอง จากนั้นตรวจสอบ 8 ช่องรอบๆ ราชา หากทุกช่องถูกครอบคลุมโดยการเดินของม้า → เช็กเมต

ตัวอย่างโค้ด 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;
        int 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;
            int ny = ky1 + j;
            if (i != 0 && j != 0) {
                if (!mpp1[{ nx, ny }]) return true;
            }
        }
    }
    return false;
}

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;
}

ผลลัพธ์

Yes its checkmate!