এই সমস্যায়, আমাদেরকে 1 দ্বারা চিহ্নিত ভরা পজিশন সহ একটি m*n চেসবোর্ড দেওয়া হয়েছে, যদি বোর্ড[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
