এই সমস্যাতে, একটি m*n চেসবোর্ড দেওয়া আছে যেখানে ভরা পজিশনগুলো ১ দিয়ে চিহ্নিত (board[i][j] = 1 মানে সেখানে কোনো পিস আছে) এবং একটি স্টার্টিং পজিশন দেওয়া আছে। আমাদের কাজ হলো বোর্ডে নাইটের মোট সম্ভাব্য মুভের সংখ্যা বের করা, ধরে নেওয়া হয়েছে সব পিস একই রঙের অর্থাৎ কোনো আক্রমণ হবে না।
চেসে নাইট হলো একটি পিস যা সব ডিরেকশনে যেতে পারে কিছু বিশেষ মুভ দিয়ে। নাইটের মুভগুলো:
দুটি হরিজন্টাল মুভ এবং একটি ভার্টিক্যাল মুভ।
দুটি ভার্টিক্যাল মুভ এবং একটি হরিজন্টাল মুভ।
উদাহরণ:
ইনপুট -
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
