ধরুন আমাদের একটি m x n বাইনারি ম্যাট্রিক্স ম্যাট আছে। এক ধাপে, আমরা একটি ঘর বেছে নিতে পারি এবং এর বিট এবং চারটি প্রতিবেশী উপস্থিত থাকলে সেটিকে ফ্লিপ করতে পারি। ম্যাটকে শূন্য ম্যাট্রিক্সে রূপান্তর করার জন্য আমাদের প্রয়োজনীয় ন্যূনতম সংখ্যক ধাপ খুঁজে বের করতে হবে। যদি কোন সমাধান না হয়, তাহলে -1 রিটার্ন করুন।
সুতরাং যদি প্রদত্ত ইনপুটটি [[0,0], [0,1]] এর মত হয় তবে পরিবর্তন হবে −
এর মত
তাই আমাদের 3টি ধাপ দরকার, আউটপুট হবে 3.
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n :=সারির সংখ্যা, m :=কলামের সংখ্যা, x :=0
- আরম্ভ করার জন্য i :=0, যখন i
- আরম্ভ করার জন্য j :=0, যখন j
- আরম্ভ করার জন্য j :=0, যখন j
- x :=x + বাম শিফট ম্যাট[i][j] মান (i * m) + j) বার সংখ্যা
- আরম্ভ করার জন্য j :=0, যখন j
- রিটার্ন dp[বর্তমান]
- করুন
- ni :=i + dir[k][0]
- nj :=j + dir[k][1]
- যদি ni <0 বা nj <0 বা ni>=n বা nj>=m হয়, তাহলে −
- নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তিতে যান
- temp :=temp XOR 2^ (ni * m) + nj)
- dp[temp] :=dp[বর্তমান] + 1
- q-তে temp সন্নিবেশ করান
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
int minFlips(vector<vector<int>>& mat) {
int n = mat.size();
int m = mat[0].size();
int x = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
x += (mat[i][j] << ((i * m) + j));
}
}
vector < int > dp(1 << (n*m), -1);
dp[x] = 0;
queue <int> q;
q.push(x);
while(!q.empty()){
int current = q.front();
q.pop();
if(current == 0)return dp[current];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
int temp = current;
temp ^= (1 << ((i *m) + j));
for(int k = 0; k < 4; k++){
int ni = i + dir[k][0];
int nj = j + dir[k][1];
if(ni < 0 || nj < 0 || ni >= n || nj >= m)continue;
temp ^= (1 << ((ni *m) + nj));
}
if(dp[temp] == -1){
dp[temp] = dp[current] + 1;
q.push(temp);
}
}
}
}
return -1;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,0},{0,1}};
cout << (ob.minFlips(v));
} ইনপুট
{{0,0},{0,1}} আউটপুট
3
