이 문제에서는 채워진 위치가 1인 m*n 체스판이 주어집니다. 즉, board[i][j] =1이면 거기에 말이 있고 시작 위치. 우리의 임무는 같은 색의 조각이 모두 있는 경우(즉, 공격이 수행되지 않는 경우) 보드에 있는 기사의 가능한 총 이동 수를 찾는 것입니다.
Knight is chess는 특별한 움직임으로 모든 방향으로 움직일 수 있는 말입니다. 체스에서 Knight의 움직임은 -
-
두 개의 수평 이동 및 수직 이동.
-
두 개의 수직 이동 및 수평 이동.
문제를 이해하기 위해 예를 들어 보겠습니다.
입력 -
board[][] = {
{ 0, 1, 0, 0 },
{ 0, 0, 1, 1 },
{ 0, 1, 1, 0 },
{ 0, 0, 0, 1 }
};
Position : (1,1) 출력 - 4
이 문제를 해결하려면 체스판에 있는 기사의 모든 가능한 움직임 중에서 유효한 움직임이 무엇인지 찾아야 합니다. 이동은 체스판에 있고 다른 말에 의해 선점되지 않은 위치에서 이동하는 경우 유효합니다.
이를 위해 우리는 주어진 위치에서 기사의 가능한 모든 움직임을 저장할 것입니다. 그런 다음 각 동작의 유효성을 확인하고 각 유효한 동작의 개수를 늘립니다.
예시
솔루션 구현을 보여주는 프로그램 −
#include <bits/stdc++.h>
#define N 8
#define M 8
using namespace std;
int countPossibleMoves(int mat[N][M], int p, int q){
int Xmoves[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int Ymoves[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int count = 0;
for (int i = 0; i < 8; i++) {
int x = p + Xmoves[i];
int y = q + Ymoves[i];
if (x>=0 && y>=0 && x<N && y<M && mat[x][y]==0)
count++;
}
return count;
}
int main(){
int mat[N][M] = { { 0, 1, 0, 0 },
{ 0, 0, 1, 1 },
{ 0, 1, 1, 0 },
{ 0, 0, 0, 1 }};
int position[2] = {1,1};
cout<<"Total number of moves possible for Knight from position ("<<position[0]<<" , "<<position[1]<<") are : ";
cout<<countPossibleMoves(mat, position[0], position[1]);
return 0;
} 출력
Total number of moves possible for Knight from position (1 , 1) are : 4