แนวคิด
ด้วยความเคารพต่อกระดานหมากรุกอนันต์ที่ให้มาโดยมีกฎเดียวกันกับหมากรุกและให้พิกัดอัศวิน N บนกระดานหมากรุกไม่มีที่สิ้นสุด (-10^9 <=x, y <=10^9) และพิกัดของกษัตริย์ ภารกิจคือการตรวจสอบว่า พระมหากษัตริย์เป็นผู้รุกฆาตหรือไม่
ป้อนข้อมูล
a1[] = { { 2, 1 }, { 1, 3 }, { 3, 6 },{ 5, 5 }, { 6, 1 }, { 7, 3 }} king -> {4, 3} ผลผลิต
Yes
พระราชาไม่สามารถเคลื่อนไหวใด ๆ ได้เนื่องจากเป็นคู่ครอง
ป้อนข้อมูล
a1 [] = {{1, 1}} king -> {3, 4} ผลผลิต
No
กษัตริย์สามารถเคลื่อนไหวได้อย่างถูกต้อง
วิธีการ
ที่นี่การเคลื่อนไหวของอัศวินนั้นผิดปกติในหมู่หมากรุก การเคลื่อนที่ของมันหันไปทางสี่เหลี่ยมจัตุรัสที่อยู่ห่างออกไปสองสี่เหลี่ยมในแนวนอน และหนึ่งสี่เหลี่ยมในแนวตั้ง หรือสองสี่เหลี่ยมในแนวตั้ง และอีกหนึ่งสี่เหลี่ยมในแนวนอน ดังนั้นการย้ายทั้งหมดจึงดูเหมือนตัวอักษร "L" ในทุกรูปแบบที่เป็นไปได้ (8 การเคลื่อนไหวที่เป็นไปได้) ด้วยเหตุนี้ ให้ใช้แผนที่แฮชของคู่เพื่อทำเครื่องหมายพิกัดที่เป็นไปได้ทั้งหมดที่อัศวินสามารถเคลื่อนที่ได้ หากพบว่าพระราชาไม่สามารถเคลื่อนไปยังพิกัดทั้ง 8 พิกัดที่อยู่ใกล้เคียงได้ เช่น หากพิกัดถูกแฮชโดยการเคลื่อนไหวของอัศวิน ก็ให้ประกาศว่าเป็น “รุกฆาต”
ตัวอย่าง
// C++ program for verifying if a king
// can move a valid move or not when
// N nights are there in a modified chessboard
#include <bits/stdc++.h>
using namespace std;
bool checkCheckMate1(pair<int, int>a1[], int n1, int kx1, int ky1){
// Pair of hash to indicate or mark the coordinates
map<pair<int, int>, int> mpp1;
// iterate for Given N knights
for (int i = 0; i < n1; i++) {
int x = a1[i].first;
int y = a1[i].second;
// indicate or mark all the "L" shaped coordinates
// that can be reached by a Knight
// starting or initial position
mpp1[{ x, y }] = 1;
// 1-st move
mpp1[{ x - 2, y + 1 }] = 1;
// 2-nd move
mpp1[{ x - 2, y - 1 }] = 1;
// 3-rd move
mpp1[{ x + 1, y + 2 }] = 1;
// 4-th move
mpp1[{ x + 1, y - 2 }] = 1;
// 5-th move
mpp1[{ x - 1, y + 2 }] = 1;
// 6-th move
mpp1[{ x + 2, y + 1 }] = 1;
// 7-th move
mpp1[{ x + 2, y - 1 }] = 1;
// 8-th move
mpp1[{ x - 1, y - 2 }] = 1;
}
// iterate for all possible 8 coordinates
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) {
// verify or check a move can be made or not
if (!mpp1[{ nx, ny }]) {
return true;
}
}
}
}
// any moves
return false;
}
// Driver Code
int main(){
pair<int, int&lgt; 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!
