Trong bài toán này, chúng ta được đưa ra một bàn cờ m * n với các vị trí được điền được đánh dấu bằng 1, tức là nếu bàn cờ [i] [j] =1, có một số quân cờ ở đó và chúng ta được đưa vị trí bắt đầu. Nhiệm vụ của chúng ta là tìm tổng số nước đi có thể có của một kỵ sĩ trong bàn cờ, nếu có tất cả các quân cùng màu tức là sẽ không có đòn tấn công nào được thực hiện.
Hiệp sĩ là cờ vua là quân có thể di chuyển theo mọi hướng với một số cách di chuyển đặc biệt. Các nước đi của Hiệp sĩ trong cờ vua là -
-
Hai bước di chuyển ngang và một bước di chuyển dọc.
-
Hai bước di chuyển dọc và một bước di chuyển ngang.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào -
board[][] = {
{ 0, 1, 0, 0 },
{ 0, 0, 1, 1 },
{ 0, 1, 1, 0 },
{ 0, 0, 0, 1 }
};
Position : (1,1) Đầu ra - 4
Để giải quyết vấn đề này, chúng ta cần tìm ra những nước đi hợp lệ trong tất cả những nước đi có thể có của một quân sĩ trong bàn cờ vua. Một nước đi có hiệu lực nếu nó đi ra khỏi vị trí trong bàn cờ và không bị chiếm trước bởi bất kỳ quân nào khác.
Đối với điều này, chúng tôi sẽ lưu trữ tất cả các bước di chuyển có thể có của hiệp sĩ từ vị trí đã cho. Và sau đó kiểm tra tính hợp lệ của mỗi nước đi và tăng số lượng cho mỗi nước đi hợp lệ.
Ví dụ
Chương trình thể hiện việc triển khai giải pháp của chúng tôi -
#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;
} Đầu ra
Total number of moves possible for Knight from position (1 , 1) are : 4