Kiểm tra xem vua có thể di chuyển một nước đi hợp lệ hay không khi N đêm có trong bàn cờ đã sửa đổi trong C ++

Khái niệm

Đối với bàn cờ vô hạn đã cho có cùng quy tắc như cờ vua và N tọa độ quân mã đã cho trên bàn cờ vô hạn (-10 ^ 9 <=x, y <=10 ^ 9) và tọa độ của nhà vua, nhiệm vụ là xác minh xem có Vua có phải là người kiểm soát hay không.

Đầu vào

a1[] = { { 2, 1 }, { 1, 3 }, { 3, 6 },{ 5, 5 }, { 6, 1 }, { 7, 3 }} king -> {4, 3}

Đầu ra

Yes

Nhà vua không thể thực hiện bất kỳ động thái nào vì nó đã được kiểm tra bạn đời.

Đầu vào

a1 [] = {{1, 1}} king -> {3, 4}

Đầu ra

No

Nhà vua có thể thực hiện các nước đi hợp lệ.

Phương pháp

Ở đây, nước đi của hiệp sĩ là không bình thường giữa các quân cờ. Chuyển động của nó hướng tới một hình vuông cách hai hình vuông theo chiều ngang và một hình vuông theo chiều dọc, hoặc hai hình vuông theo chiều dọc và một hình vuông theo chiều ngang. Vì vậy, nước đi hoàn chỉnh trông giống như chữ “L” trong mọi hình dạng có thể (8 nước đi có thể). Kết quả là, hãy áp dụng một bản đồ băm của các cặp để đánh dấu tất cả các tọa độ có thể có mà kỵ sĩ có thể di chuyển. Nếu người ta thấy rằng Nhà vua không thể di chuyển đến bất kỳ tọa độ nào trong số 8 tọa độ gần đó của nó, tức là nếu tọa độ được băm bởi nước đi của hiệp sĩ, thì nó được tuyên bố là "người kiểm tra".

Ví dụ

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

Đầu ra

Yes its checkmate!