C++에서 수정된 체스판에 N 밤이 있을 때 왕이 유효한 이동을 이동할 수 있는지 확인하십시오.

개념

주어진 무한체스판과 같은 규칙으로 무한체스판에 주어진 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

왕은 유효한 움직임을 할 수 있습니다.

방법

여기에서 기사의 움직임은 체스 말 중에서 이례적입니다. 그 움직임은 수평으로 2칸, 수직으로 1칸, 또는 수직으로 2칸, 수평으로 1칸 떨어진 정사각형을 향해 있습니다. 따라서 완전한 움직임은 가능한 모든 모양에서 문자 "L"처럼 보입니다(8개의 가능한 움직임). 그 결과 기사가 이동할 수 있는 모든 가능한 좌표를 표시하기 위해 쌍의 해시 맵을 적용합니다. King이 근처 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!