ในปัญหานี้ เราได้รับกระดานหมากรุก m*n ที่มีตำแหน่งที่เต็มแล้วทำเครื่องหมายด้วย 1 คือถ้า board[i][j] = 1 มีชิ้นอยู่ที่นั่น และเราได้รับตำแหน่งเริ่มต้น งานของเราคือหาจำนวนการเคลื่อนที่ที่เป็นไปได้ทั้งหมดสำหรับ knight ในกระดาน หากชิ้นทั้งหมดเป็นสีเดียวกัน คือไม่มีการโจมตี
Knight ในหมากรุกคือชิ้นที่สามารถเคลื่อนที่ในทุกทิศทางด้วยการเคลื่อนที่พิเศษบางอย่าง การเคลื่อนที่ของ Knight ในหมากรุกคือ:
สองการเคลื่อนที่แนวนอนและหนึ่งการเคลื่อนที่แนวตั้ง
สองการเคลื่อนที่แนวตั้งและหนึ่งการเคลื่อนที่แนวนอน
มาดูตัวอย่างเพื่อเข้าใจปัญหา:
Input -
board[][] = {
{ 0, 1, 0, 0 },
{ 0, 0, 1, 1 },
{ 0, 1, 1, 0 },
{ 0, 0, 0, 1 }
};
Position : (1,1)
Output - 4
เพื่อแก้ปัญหานี้ เราต้องหาว่าการเคลื่อนที่ใดเป็นไปได้จากการเคลื่อนที่ทั้งหมดของ knight ในกระดานหมากรุก การเคลื่อนที่เป็นไปได้หากมันเคลื่อนที่ออกจากตำแหน่งที่อยู่ในกระดานหมากรุกและไม่ได้ถูกครอบครองโดยชิ้นอื่นล่วงหน้า
สำหรับสิ่งนี้ เราจะเก็บการเคลื่อนที่ที่เป็นไปได้ทั้งหมดของ knight จากตำแหน่งที่กำหนด และตรวจสอบความถูกต้องของแต่ละการเคลื่อนที่และเพิ่มจำนวนสำหรับแต่ละการเคลื่อนที่ที่ถูกต้อง
ตัวอย่าง
โปรแกรมแสดงการนำโซลูชันของเราไปใช้งาน:
#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
